A* Search: Dijkstra With a Sense of Direction
Published on · In Software Engineeringby Steven Brown
A* is a shortest-path algorithm that adds one piece of information to Dijkstra's: an estimate of how far each node is from the goal. Dijkstra expands nodes in order of the cost to reach them, which means it grows outward evenly in every direction until it happens to touch the goal. A* expands nodes in order of the cost to reach them plus the estimated cost remaining, so the search leans toward the goal and leaves most of the graph untouched.
The estimate is called the heuristic, and nearly everything interesting about A* is a property of it. A good heuristic cuts the work by an order of magnitude and still returns the optimal path. A heuristic that overestimates returns a path faster but gives up the guarantee that it is the shortest one. A heuristic of zero turns A* back into Dijkstra. On the grid measured below, Dijkstra expanded 31,864 cells to cross it; A* with a Manhattan-distance heuristic expanded 3,105 and returned a path of identical cost.
