A* is Dijkstra with a sense of direction. To the cost already paid, g(n), it adds a guess of the cost still to come, h(n), and always expands the node with the smallest f = g + h. It is provably optimal — but only while the guess never lies. Let h over-estimate and the guarantee dies. Down the center, the graph goes in, the frontier is worked, the path comes out. The blue team builds and defends it; the red team tries to break it.
source Hart, Nilsson & Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths (1968), IEEE Trans. Systems Science & Cybernetics 4(2):100–107 — doi:10.1109/TSSC.1968.300136. Rendered, not quoted.
Every node on the frontier carries a score. g(n) is the exact cost of the cheapest path found to n; h(n) estimates the cost from n to the goal. A* pops the node of least f = g + h, expands it, and stops the instant it pops the goal.
Two honesty conditions on h matter:
admissible — h(n) never over-estimates the true remaining cost. This alone makes A* return the optimal path. consistent — h(u) ≤ w(u,v) + h(v) for every edge. This stronger promise means no node is ever re-opened: each is expanded at most once.
Set h(n) = 0 everywhere and f collapses to g: A* becomes Dijkstra exactly — same expansions, same result. The witness (window 7) checks this equality live.
Hart, Nilsson and Raphael (1968) added one thing to Dijkstra (1959): a lower bound on the road ahead. That single addition is the whole of pathfinding and planning — games, routing, robot motion. Each sphere is the next one's premise: Dijkstra guided toward the goal is A*.
The blue team's live check: re-run the engine and confirm four claims — admissible A* matches brute force, h=0 matches Dijkstra's expansions, a consistent run expands each node once, and the reference graph's optimum is returned. If red tampers, this badge is where it shows.
A weighted graph of six nodes on a grid. Start is S; you choose the goal. Every edge weight equals the Manhattan distance between its endpoints, so the Manhattan-to-goal estimate is consistent by construction (the triangle inequality) — and therefore admissible.
| node | coord (x,y) | h to G = (4,3) |
|---|---|---|
| S | 0, 0 | 7 |
| A | 2, 0 | 5 |
| B | 0, 2 | 5 |
| C | 2, 2 | 3 |
| D | 4, 1 | 2 |
| G | 4, 3 | 0 |
Edges (weight): S-A 2, S-B 2, A-C 2, B-C 2, A-D 3, C-D 3, C-G 3, D-G 2. That is what you feed the panel below.
Accent edges = the returned path; cyan-rimmed nodes = expanded. Change the heuristic and watch the frontier shrink.
open set at each pop, ordered by f:
| # | pop | g | h | f | open (node:f) |
|---|
Nothing is looked up — every g, h, f, and the returned path are computed on the spot from f = g + h.
What the machine produces, proven: with an admissible heuristic the returned path's cost is exactly the brute-force optimum over all simple paths — equal to Dijkstra, checked live. With h = 0 it reproduces Dijkstra's expansion order node-for-node. A better heuristic keeps the answer optimal while expanding fewer nodes — that is the whole point of A*.
The blue team's witness (left) confirms these claims live; the red team (right) tries to make them wrong.
And even when it is correct, it is not free: A* stores the whole open and closed frontier, which in the worst case is exponential in the solution depth — the same blow-up as breadth-first search. On an adversarial graph with a useless heuristic it degrades straight back to Dijkstra. The hard, unsolved part is not the search — it is designing an h that is both cheap and tight.
"A* always finds the shortest path." Cut. Only with an admissible heuristic. The tamper below exhibits a graph where an over-estimating h returns cost 4 when the true shortest is 2.
"A* needs a consistent heuristic to be optimal." Corrected. Admissibility alone gives optimality (with re-opening); consistency is the extra promise that buys single-expansion — no node re-opened.
"A bigger heuristic is always better." Cut. Bigger expands fewer nodes only up to admissibility. Past the true remaining cost, "faster" becomes "wrong."
"A* is always faster than Dijkstra." Kept, corrected. With h=0 it is Dijkstra; a bad h adds overhead for nothing. Faster is earned by a good heuristic, not guaranteed.
The red team's move: inflate the heuristic at one node so it over-estimates the true remaining cost — then still claim the path is optimal. The blue team's witness (window 7) is watching the reference graph.
Over-estimate the remaining cost at node A and A* pops the goal via a longer route before it ever reaches the true-cheapest one — the witness recomputes the returned cost against brute force, sees it is no longer the optimum, and turns red. Nothing is faked; the attack is real and it is caught.