12 A* Algorithm

A* is presented as an informed shortest-path search that improves on Dijkstra’s algorithm by using both the cost already paid and an estimate of the cost still remaining. Instead of expanding outward blindly in all directions, it biases exploration toward the goal with a heuristic h(n), such as straight-line distance on road maps or Manhattan distance on grids. The key requirement is that the heuristic be admissible, meaning it never overestimates the true remaining cost, so the algorithm stays optimal while becoming much more selective about which nodes to examine.

The chapter explains A* through the values g(n), h(n), and f(n) = g(n) + h(n). The priority queue always chooses the node with the smallest f value, while g tracks the exact cost from the start and h estimates the remaining distance to the goal. A worked example shows how A* expands nodes, rejects worse routes, updates parent pointers, and does not stop the first time it sees the goal; it stops only when the goal itself is removed from the queue, which is what preserves the guarantee of finding the cheapest path.

Beyond the core algorithm, the chapter highlights why A* matters in practice and where its limits appear. It is widely used in navigation systems, game AI, and puzzle solving because a good heuristic can drastically reduce search effort. However, the worst-case time can still resemble Dijkstra’s, and memory usage can become the main bottleneck because A* must store many discovered nodes and their bookkeeping data. This leads to variants such as IDA*, which reduce memory needs by trading away some repeated work, and to other alternatives like weighted A* or greedy best-first search when speed matters more than exact optimality.

The graph shows the starting position before any search has started. Every intersection has its own heuristic h(n) attached. Node S is the starting node and a queue to track the heuristic.

After expanding S, A and B enter the priority queue. A has the lower estimated total cost, f = g + h (7 versus 8), so A* selects it next. Expanding A proposes a route to B with cost g = 5, but A* rejects it because B already has a cheaper route from S with g = 4. C is added with f = 8, and B and C now tie in the estimated total cost.

A* expands B and discovers D with g = 8 and f = 10. C still has the lower priority value, f = 8, so it will be expanded before D. Expanding C gives another route to D with the same cost, so D’s existing value is unchanged. C also reaches G with a cost of 11, but A* does not stop at first discovering the goal, D still has a lower priority value and may lead to a cheaper route.

Expanding D finds a better route to G: the path through D costs 10, improving on the previous cost of 11. A* updates G’s cost and parent pointer to record this route. G is now the lowest-cost node in the queue, so A* removes it and ends the search. Following the parent pointers gives S → B → D → G, with total cost 4 + 4 + 2 = 10.

ALT strengthens A*’s heuristic by using distances precomputed from selected landmarks. The triangle inequality lets those known distances provide a lower-bound estimate of the remaining route cost, often more informative than straight-line distance alone.

A* searches a grid with obstacles between the start and goal. The heuristic favors progress toward the goal, while the path cost accounts for the detour around blocked cells; together, these guide the search to a valid shortest route.

For a sliding-tile puzzle, the Manhattan-distance heuristic adds up how many rows and columns each tile is away from its goal position. It estimates a minimum amount of remaining movement, because it counts each tile’s displacement while ignoring interference from other tiles.

• Informed search is adding a heuristic estimate of remaining cost so the search leans toward the goal instead of exploring uniformly in every direction, the way Dijkstra's algorithm does.
• A heuristic, h(n), is a cheap-to-compute guess at the remaining cost from a node to the goal: straight-line distance for road maps, Manhattan distance for grid movement, and summed tile-displacement for sliding puzzles.
• A heuristic must be admissible. It can never overestimate the true remaining cost, or A* loses its guarantee of finding the shortest path.
• Four admissible heuristics across different problem domains were collected side by side, showing the same underlying idea, a provable lower bound on true cost, repeating in different disguises.
• A* tracks two numbers per node: g(n), the real cost paid so far, and h(n), the estimated cost still ahead. It always expands whichever node minimizes f(n) = g(n) + h(n).
• A* was traced step by step on a six-intersection map, watching the priority queue evolve one expansion at a time instead of jumping straight to the final answer.
• The trace showed A* rejecting a worse route (reaching B through A) and later replacing an already-queued value for G with a cheaper one found through D. Both are normal, expected bookkeeping, not corrections of a mistake.
• The trace also demonstrated why A* can't stop the moment it first sees the goal: G appeared on the queue partway through but wasn't the cheapest entry yet, and stopping there would have reported a path one unit more expensive than optimal.
• Consistency, a property stronger than admissibility, guarantees a node is never reopened once expanded. That held for every heuristic used in the chapter, and it's the reason the worked trace never had to undo a settled node.
• A* was given as pseudocode, matched line by line against the worked trace, and its complexity was established: O((V + E) log V) time in the worst case, matching Dijkstra, with memory as the more common practical bottleneck, which motivated Korf's 1985 IDA* variant.

1. Code implementation: https://github.com/aniketwattamwar/Algorithms-Every-Programmer-Should-Know
2. Hart, P. E., Nilsson, N. J., and Raphael, B. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” IEEE Transactions on Systems Science and Cybernetics, SSC-4(2), 1968.
3. Goldberg, A. V., and Harrelson, C. “Computing the Shortest Path: A* Search Meets Graph Theory.” Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005.
4. Korf, R. E. “Depth-First Iterative-Deepening: An Optimal Admissible Tree Search.” Artificial Intelligence, 27(1), 1985.
5. Patel, A. “Amit's A* Pages.” Stanford University. https://theory.stanford.edu/~amitp/GameProgramming/

FAQ