V
 the graph vertex typeE
 the graph edge typeAStarShortestPath
@Deprecated public class AStarShortestPath<V,E> extends Object
getShortestPath(Object, Object, AStarAdmissibleHeuristic)
getShortestPath} 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!
Modifier and Type  Field and Description 

protected AStarAdmissibleHeuristic<V> 
admissibleHeuristic
Deprecated.

protected Map<V,E> 
cameFrom
Deprecated.

protected Set<V> 
closedList
Deprecated.

protected Map<V,Double> 
gScoreMap
Deprecated.

protected int 
numberOfExpandedNodes
Deprecated.

protected FibonacciHeap<V> 
openList
Deprecated.

protected Map<V,FibonacciHeapNode<V>> 
vertexToHeapNodeMap
Deprecated.

Constructor and Description 

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

Modifier and Type  Method and Description 

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

GraphPath<V,E> 
getShortestPath(V sourceVertex,
V targetVertex,
AStarAdmissibleHeuristic<V> admissibleHeuristic)
Deprecated.
Calculates (and returns) the shortest path from the sourceVertex to the targetVertex.

boolean 
isConsistentHeuristic(AStarAdmissibleHeuristic<V> admissibleHeuristic)
Deprecated.
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
public GraphPath<V,E> getShortestPath(V sourceVertex, V targetVertex, AStarAdmissibleHeuristic<V> admissibleHeuristic)
sourceVertex
 source vertextargetVertex
 target vertexadmissibleHeuristic
 admissible heuristic which estimates the distance from a node to
the target node.public 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 Euclidian
distance, are consistent heuristics.admissibleHeuristic
 admissible heuristicCopyright © 2017. All rights reserved.