A* Algorithm

The A* algorithm is similar to Dijkstra's algorithm, except that it puts entries into the priority queue based on the f value (estimated total cost) rather than g value (lowest cost found so far).

Note that A* does not recognize that a node is a goal until the node is removed from the priority queue.

Theorem: If the h function does not over-estimate the distance to the goal, A* finds an optimum path.

A* will get the same result as Dijkstra's algorithm while doing less work, since Dijkstra searches all nodes while A* searches only nodes that may be on a path to the goal.