A* search

The problem it solves

Dijkstra answers “shortest path from here to everywhere” — and pays for that generality by expanding outward in all directions like a ripple, even when you only care about one destination sitting plainly to the northeast. A* is the point-to-point specialist: give it an optimistic estimate of the remaining distance from any node to the goal — for maps, the straight-line distance — and it steers the same machinery toward the target, expanding a lens-shaped sliver of the graph instead of a disc, while still guaranteeing the optimal route.

This is the algorithm inside satnav routing, game-character pathfinding, robot motion planning, and puzzle solvers from the 15-puzzle to protein folding — anywhere a domain offers a cheap, never-overestimating guess of “how far is left”. Its intellectual content is exactly one idea: order the priority queue not by cost-so-far (g), and not by estimated-cost-remaining (h), but by their sum f = g + h — the optimistic estimate of the whole route through this node. Everything else, verbatim, is Dijkstra.

The intuition — and where it breaks down

Hiking toward a visible mountain, you weigh two things at every fork: how far you have already walked down this branch (g), and how far the mountain still looks from there (h). A branch that has consumed little distance but points away from the mountain scores badly; a longer branch aimed straight at it scores well. A* institutionalises the instinct: always continue from the open node with the smallest g + h.

The guarantee has a precise price of admission: h must never overestimate the true remaining cost — the admissibility condition. A straight line never overestimates road distance, which is why maps are A*’s home turf. The proof sketch is worth carrying: when the goal comes off the queue with f = g(goal), every other open node has f ≥ that value, and since their f-values are optimistic estimates of any route through them, no route through any of them can beat the goal’s g. First expansion of the goal = optimal route, full stop.

Break admissibility and the guarantee dies quietly: an overestimating h makes an inferior route to the goal look finished while the better route still waits, and the algorithm returns it with full confidence. (Weighted A* does this deliberately — multiply h by 1.2 and you get answers at most 20% worse, often much faster; the sin is doing it unknowingly.) The other boundary conditions are illuminating: h = 0 is exactly Dijkstra, and a perfect h expands only the optimal path itself. Every real heuristic buys a point between those extremes — heuristic design is choosing where.

Loading…

A walkthrough you can check

In the player’s road-map graph, edge weights are the drawn lengths, so the straight-line heuristic is honest by construction. Watch three moments.

1. The first expansions: the open set’s f-values are printed as each node is expanded — g climbing, h falling as the wave leans toward the target. Nodes geometrically behind the start have large h and sink in the queue, often never expanded at all. Compare the expanded counter against the node total in the title block.
2. A steering decision: the prediction prompt pauses on “which node expands next?” — answered not by cheapest g (Dijkstra’s rule) but by smallest g + h. Getting this wrong in exactly the Dijkstra direction is the point of asking.
3. The finish: when the target is expanded, the route inks in along parent pointers, and the summary reports how many nodes were expanded versus how many exist. On this graph the savings are modest — small dense graphs are Dijkstra-friendly — and that honesty matters: the compass pays in proportion to how much graph lies away from the goal.

For a hand-check, take any expanded node the trace annotates with g, h, f and verify f = g + h, then verify the expansion order is non-decreasing in f. Both facts together are the algorithm.

The invariant

Nodes are expanded in non-decreasing f-order, and with admissible h, the first expansion of the goal carries an optimal path. The queue delivers the first half directly (with the same lazy-deletion caveat as Dijkstra). The second half: suppose the goal is expanded with cost g*, while some cheaper route R exists. R has an open node u somewhere (its frontier crossing); f(u) = g(u) + h(u) ≤ true cost of R < g* — admissibility gives the ≤ — so u’s f beats the goal’s, and u would have been expanded first. Contradiction; there is no cheaper R.

A second condition, consistency (h(u) ≤ weight(u,v) + h(v) for every edge — a triangle inequality), upgrades the guarantee: g(u) is final the first time u is expanded, so no node ever needs re-expansion, and the closed set is permanently closed. Straight-line distance is consistent; most natural heuristics are. Admissible-but-inconsistent heuristics do exist and force re-expansions — the standard textbook subtlety, worth one sentence in an interview and rarely more.

Complexity, derived

Same skeleton as Dijkstra: every edge relaxed at most once per settled endpoint, heap operations at O(log V) — O(E log V) worst case, hit exactly when h = 0 or the heuristic is useless. The interesting quantity is not the bound but the expansion count: A*’s practical cost is proportional to the number of nodes whose f does not exceed the optimal cost, and a sharp heuristic shrinks that set toward the optimal path itself. On a road network, Dijkstra from London to Edinburgh expands a disc reaching Cornwall; A* expands a corridor up the map. Same worst case, an order of magnitude apart in practice — the trace’s expanded counter is this argument in miniature.

Memory is the quiet constraint: the open set can hold a large frontier, and puzzle-space searches (where “graph” means implicit states) run out of RAM before time. IDA* and frontier search exist for exactly that regime — names worth knowing, algorithms rarely worth coding live.

What people get wrong

• Ordering by h alone: greedy best-first search — fast, aims straight at the goal, and happily returns non-optimal routes. The g term is not decoration; it is the ledger.
• An inadmissible heuristic by accident: estimating remaining cost with average speed on a fast road, or rounding distances up, silently voids the warranty. When weights are rounded lengths, scale h down by the rounding margin — this site’s implementation does, and says so in a comment.
• Recomputing h per comparison: cache f on the heap entry at push time.
• Skipping stale-entry checks: same lazy-deletion idiom as Dijkstra and Prim; a popped node already expanded is discarded.
• Testing only that “a path was found”: the failure mode of a broken A* is a suboptimal path, not a missing one. Referee against Dijkstra on the same graph — the unit suite here does.

Implementation notes

Take a working Dijkstra and change two lines: seed the queue with (h(start), start), and push (g + weight + h(next), next) instead of (g + weight, next). Store g separately from f — g is the truth, f is the ordering — and keep parents for reconstruction. Everything else, including the lazy-deletion pop, transfers unchanged.

Heuristics by domain: straight-line (Euclidean) for maps; Manhattan distance for 4-connected grids; diagonal/Chebyshev for 8-connected; landmark heuristics (ALT) precompute Dijkstra from a few pivots and use triangle-inequality bounds — the production choice for continental road networks alongside contraction hierarchies. For puzzles, pattern databases memoise exact solve-costs of abstracted subproblems. The engineering rule: h should be cheap (it runs per push) and tight (savings scale with it); when two admissible heuristics exist, their max is admissible and at least as tight.

Tie-breaking deserves one deliberate line: many nodes share f along the optimal corridor, and breaking ties toward larger g (deeper progress) empirically halves expansions on grids. And when the goal moves or many queries share a graph, look up bidirectional A* and contraction hierarchies before hand-rolling anything.

The follow-up questions

What exactly must be true of h? Admissible — never overestimate — for optimal answers; consistent — triangle inequality across edges — to also never re-expand. Straight-line distance on real distances is both.

What happens if h overestimates? The goal can be expanded via an inferior route while the true best route waits, and the algorithm returns confident nonsense. Weighted A* exploits this knowingly for bounded suboptimality; doing it unknowingly is just a bug.

h = 0? Perfect h? Dijkstra; and expansion of exactly the optimal path. A* interpolates, and heuristic quality decides where on the line you land.

Why not always use A?* It answers one (start, goal) pair; Dijkstra’s single run answers a whole source’s distances. No usable heuristic — abstract graphs with no geometry — also degrades A* to Dijkstra plus overhead. And in memory-bound implicit-graph search, the open set itself becomes the enemy — IDA* territory.