V
 the graph vertex typeE
 the graph edge typepublic class AStarShortestPath<V,E> extends Object
getPath(Object, Object)
method; no new instance of this class has to be created. The
heuristic is implemented using a FibonacciHeap data structure to maintain the set of open nodes.
However, there still exist several approaches in literature to improve the performance of this
heuristic which one could consider to implement. Another issue to take into consideration is the
following: given two candidate nodes, i, j to expand, where f(i)=f(j), g(i)>g(j),
h(i)<g(j), f(i)=g(i)+h(i), g(i) is the actual distance from the source node to i, h(i) is the
estimated distance from i to the target node. Usually a depthfirst search is desired, so ideally
we would expand node i first. Using the FibonacciHeap, this is not necessarily the case though.
This could be improved in a later version.
Note: This implementation works with both consistent and inconsistent admissible heuristics. For
details on consistency, refer to the description of the method
isConsistentHeuristic(AStarAdmissibleHeuristic)
. However, this class is not
optimized for inconsistent heuristics. Several opportunities to improve both worst case and
average runtime complexities for A* with inconsistent heuristics described in literature can be
used to improve this implementation!
ShortestPathAlgorithm.SingleSourcePaths<V,E>
Modifier and Type  Field and Description 

protected AStarAdmissibleHeuristic<V> 
admissibleHeuristic 
protected Map<V,E> 
cameFrom 
protected Set<V> 
closedList 
protected Comparator<Double> 
comparator 
protected Graph<V,E> 
graph
The underlying graph.

protected Map<V,Double> 
gScoreMap 
protected int 
numberOfExpandedNodes 
protected FibonacciHeap<V> 
openList 
protected Map<V,FibonacciHeapNode<V>> 
vertexToHeapNodeMap 
Constructor and Description 

AStarShortestPath(Graph<V,E> graph,
AStarAdmissibleHeuristic<V> admissibleHeuristic)
Create a new instance of the A* shortest path algorithm.

Modifier and Type  Method and Description 

protected GraphPath<V,E> 
createEmptyPath(V source,
V sink)
Create an empty path.

int 
getNumberOfExpandedNodes()
Returns how many nodes have been expanded in the A* search procedure in its last invocation.

GraphPath<V,E> 
getPath(V sourceVertex,
V targetVertex)
Calculates (and returns) the shortest path from the sourceVertex to the targetVertex.

ShortestPathAlgorithm.SingleSourcePaths<V,E> 
getPaths(V source)
Compute all shortest paths starting from a single source vertex.

double 
getPathWeight(V source,
V sink)
Get the weight of the shortest path from a source vertex to a sink vertex.

boolean 
isConsistentHeuristic(AStarAdmissibleHeuristic<V> admissibleHeuristic)
Returns true if the provided heuristic is a consistent or monotone heuristic
wrt the graph provided at construction time.

protected FibonacciHeap<V> openList
protected Map<V,FibonacciHeapNode<V>> vertexToHeapNodeMap
protected AStarAdmissibleHeuristic<V> admissibleHeuristic
protected int numberOfExpandedNodes
protected Comparator<Double> comparator
protected final Graph<V,E> graph
public AStarShortestPath(Graph<V,E> graph, AStarAdmissibleHeuristic<V> admissibleHeuristic)
graph
 the input graphadmissibleHeuristic
 admissible heuristic which estimates the distance from a node to
the target node. The heuristic must never overestimate the distance.public GraphPath<V,E> getPath(V sourceVertex, V targetVertex)
sourceVertex
 source vertextargetVertex
 target vertexpublic int getNumberOfExpandedNodes()
public boolean isConsistentHeuristic(AStarAdmissibleHeuristic<V> admissibleHeuristic)
h(u)≤ d(u,v)+h(v)
, for every edge
(u,v), where d(u,v) is the weight of edge (u,v) and h(u) is the estimated cost to reach the
target node from vertex u. Most natural admissible heuristics, such as Manhattan or Euclidean
distance, are consistent heuristics.admissibleHeuristic
 admissible heuristicpublic ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)
getPaths
in interface ShortestPathAlgorithm<V,E>
source
 the source vertexpublic double getPathWeight(V source, V sink)
Double.POSITIVE_INFINITY
if no path exists.getPathWeight
in interface ShortestPathAlgorithm<V,E>
source
 the source vertexsink
 the sink vertexDouble.POSITIVE_INFINITY
if no path existsprotected final GraphPath<V,E> createEmptyPath(V source, V sink)
source
 the source vertexsink
 the sink vertexCopyright © 2017. All rights reserved.