A* Search

The 10-second versionCopy Anchor Link

A* is Dijkstra with a sense of direction. Instead of always expanding the node with the smallest cost from the start, it expands the node with the smallest f = g + h, where g is the real cost so far and h is a heuristic guess of the remaining cost to the goal. If h never overestimates the true remaining cost (admissible) and plays nicely along edges (consistent), A* still returns the optimal path — but it touches a tiny fraction of the nodes Dijkstra would, as long as the guess actually knows something. Get the heuristic wrong and you lose optimality; set it to zero and you are back to plain Dijkstra.

Why this existedCopy Anchor Link

By the late 1960s, robots were about to have to find their own way around. At the Stanford Research Institute (SRI), a project was building Shakey — the first mobile robot that could reason about its own actions, named for the way it wobbled when it moved. Shakey needed to plan routes through a building: a goal, a map, and a graph of rooms and doorways. Dijkstra could do it, but it spread out in every direction like water, exploring rooms behind it just as eagerly as rooms in front. That is wasteful when you know where you are going.

Earlier work had already tried to exploit that knowledge. In 1966, Doran and Michie built the Graph Traverser, which used a heuristic estimate to decide what to explore next — fast, but with no guarantee of finding the best path.

Then in 1968, Peter Hart, Nils Nilsson, and Bertram Raphael published "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." They took the heuristic idea and, crucially, proved when it is safe: order by g + h, and as long as the heuristic never overestimates, the answer is optimal. The asterisk in the name was their notation for "this search is admissible with this heuristic."

Why it mattered: it was the first search that was both fast and provably correct. That combination is why, half a century later, A* is still the default pathfinder in game engines, mapping software, and robotics.

Inside the inventor's headCopy Anchor Link

Think about what the three candidate strategies actually do:

• Greedy best-first expands the node with the smallest h alone — it beelines toward the goal. Blazing fast, and wrong: a tempting straight line can lead into a dead end, and greedy search never looks back to the cheaper detour.
• Dijkstra expands the smallest g — the cost so far. Always correct, but blind: it explores in a uniform blob and only stops when it happens to reach the goal.
• Neither is what a human navigator does. A person reasons with both: "I have paid this much so far, and the goal still looks that far away."

The pivot is to add them. Order the frontier by f = g + h, and the search is pulled toward the goal while still accounting for the cost already sunk in. Then prove it: if h never exceeds the true remaining cost, then f never exceeds the true total cost of a path through that node, so the search can never be lured past a better route. That is the theorem that makes it a real algorithm instead of a heuristic gamble.

The final approachCopy Anchor Link

The algorithmCopy Anchor Link

1. Set g[source] = 0; push the source into the open set with key h(source).
2. Pop the node u with the smallest f = g + h. Skip it if the entry is stale.
3. If u is the goal, reconstruct the path and stop — with a consistent heuristic, the first goal pop is already optimal.
4. For each neighbor v with edge weight w: tentative = g[u] + w. If it is smaller than g[v], set g[v], compute f[v] = g[v] + h(v), and push v.
5. Repeat until the goal is popped or the open set empties.

The invariantsCopy Anchor Link

• Admissible. h(n) ≤ the true cost from n to the goal, for every node. This is what guarantees A* never returns a path longer than optimal.
• Consistent (monotonic). h(u) ≤ w(u, v) + h(v) for every edge. This keeps f non-decreasing along any path, so no node ever needs re-expanding and the first time the goal is popped, its g is final.
• The special case. Set h ≡ 0 and A* collapses exactly into Dijkstra — which is the cleanest proof that A* is a generalization, not a different animal.

Heuristic search, step by stepCopy Anchor Link

Take four nodes with coordinates S = (0,0), A = (1,0), B = (2,0), G = (3,0), edges S→A = 1, S→B = 5, A→B = 1, A→G = 10, B→G = 1. Use straight-line distance as the heuristic:

Two things worth noticing. First, B was first reached at cost 5, then improved to 2 when A discovered a cheaper route — just like Dijkstra, A* rewrites distances. Second, the heuristic steered the search straight down the line (S, A, B, G) and never wasted effort on the A→G = 10 edge's tempting endpoint. Look at what the shapes of the two searches do on a grid:

It in codeCopy Anchor Link

function aStar(adj, h, src, goal) {  const g = new Array(adj.length).fill(Infinity);  g[src] = 0;  const open = [[h[src], src]];              // [f, node] — a heap is faster  while (open.length) {    open.sort((a, b) => a[0] - b[0]);    const [, u] = open.shift();    if (u === goal) return g[goal];          // first pop of the goal is optimal    for (const [v, w] of adj[u]) {      if (g[u] + w < g[v]) {                 // relax        g[v] = g[u] + w;        open.push([g[v] + h[v], v]);      }    }  }  return Infinity;                           // unreachable}

ComplexityCopy Anchor Link

In the worst case A* is no faster than Dijkstra — a bad heuristic gives you nothing. The whole payoff is the practical node count: on a grid with a decent distance heuristic, A* typically expands a small fraction of what Dijkstra does for the same optimal answer.

Where you meet it todayCopy Anchor Link

• Games. Nearly every tile-grid and navmesh pathfinder — StarCraft, Age of Empires, Unity's and Unreal's built-in navigation — is A* under the hood, usually tuning the heuristic to make units look natural.
• Maps and route planning. Real road routers use A* with a travel-time heuristic, then layer on tricks like contraction hierarchies to stay interactive at country scale.
• Robotics. It started with Shakey, and it is still here: mobile robots plan with A* and its incremental cousins (D*-Lite) when the world changes underneath them.
• Puzzle solvers. The 8-puzzle or 15-puzzle with Manhattan distance as the heuristic, and Rubik's-cube solvers with an IDA* variant, are textbook A* applications.

The heuristic is the whole game, and on a grid the classic admissible one is Manhattan distance — it can never overestimate on a four-directional grid, so it never breaks optimality:

// admissible on a 4-directional grid: never overestimatesconst manhattan = (x, y, gx, gy) =>  Math.abs(x - gx) + Math.abs(y - gy);

RecapCopy Anchor Link

• A* orders expansion by f = g + h: the real cost so far plus a guess of the cost remaining.
• An admissible h (never overestimating) keeps the result optimal; a consistent h means the first time you pop the goal, it is final.
• h ≡ 0 turns A* back into Dijkstra; drop g instead and you get greedy best-first, which is fast but not optimal.
• Worst-case time matches Dijkstra at O((V + E) log V), but a good heuristic slashes the nodes actually explored.
• Born on Shakey at SRI in 1968, it is now the default pathfinder in games, maps, and robotics.

Next up: Divide & Conquer — the graph track ends here and the paradigm track begins by splitting problems cleanly in half.