590
Graph Algorithms
F to make its choice and Dijkstra’s algorithm uses G,
but F = G + H . Dijkstra’s algorithm is therefore a*
with a heuristic function that always returns 0. By using a non-zero heuristic H value, a* makes smarter
choices (and therefore closes in on the shortest path
faster) provided, of course, that the heuristic function
is a good guess. If the heuristic function consistently
overestimates the distance to the target, then the path
computed will not be the shortest path. Another way
to look at the difference between a* and Dijkstra’s
algorithm is to remember that Dijkstra’s algorithm is
a greedy algorithm—it makes its decisions based on
the local knowledge of how close adjacent nodes are to
p. a* uses global knowledge (or assumed global
knowledge) about not only how close adjacent nodes
are to p but also how far they are from the target node.
http://www.policyalmanac.org/games/aStarTutorial.htm
http://www.heyes-jones.com/astar.html