A* search

In short: A* (A-star) finds the shortest path in a graph faster than Dijkstra by preferring to search toward the goal using an estimate (a “heuristic”).

In more detail: A* rates each node with f = g + h. Here g is the known cost from the start and h the estimated remaining distance to the goal. The node with the smallest f is examined next.

In Depth

• Heuristic: Must underestimate or exactly match the remaining cost (admissible) so the shortest path is guaranteed. On grid maps, Manhattan distance works well.
• Data structure: A priority queue (heap) delivers the best node quickly.
• Special case: With h = 0, A* becomes Dijkstra’s algorithm.
• Use: Pathfinding in games, navigation, robotics.
• Memory: A* remembers many nodes and can need a lot of memory on very large maps.

See also: Dijkstra’s algorithm, Graph (data structure)