Thought Toys · Strategy & computation · Exhibit 36
Dijkstra floods outward evenly until it happens to reach the goal. A* instead guesses — it favors squares that look closer to the goal — and explores far fewer of them for free. Push that guess too hard, though, and the search can lock in a longer, wrong route before the true shortest one is ever found.
Find the way across
Turn up the guess and watch the search narrow.
A maze of squares, some blocked. Getting from the start to the goal costs one step per square. Dijkstra (exhibit 26's engine) finds the cheapest route by growing outward from the start in every direction at once, like a ripple — reliable, but it wastes effort exploring squares that lead nowhere near the goal.
A* adds a guess: for every square it's considering, it adds a heuristic — an estimate of the remaining distance, here the straight-line (Manhattan) distance to the goal, and explores the most promising-looking square first. Turn the guess dial to 1 and the search is still provably exact — same answer as Dijkstra — but it visits far fewer squares, because the guess is never overconfident: it can under-promise (a wall might make the true route longer) but never over-promise. That's an admissible heuristic — one that never overestimates the true remaining cost, and it's the whole reason A* can be both fast and correct.
Push the dial past 1 and the guess starts to dominate the cost actually paid so far. On this maze, once it crosses roughly 4, the search convinces itself a longer route is fine because a few of its squares look close to the goal — and by the time the true shortest route would have been found, the search has already locked in the wrong answer and stopped. Hit show the true shortest route to see exactly how much longer the wrong one is.
improve/verify/36-astar.js): at w≤1 this matches an independent breadth-first
reference on 263 solvable random mazes, every single time; on the maze shown here, w=1 finds the
true shortest route (36 steps) while exploring markedly fewer squares than w=0 (plain Dijkstra);
past w=4 the route jumps to 52 steps — a real 44% detour, not a rounding error.
Counter-example: on an obstacle-free grid, no weight — however large — ever produces a
wrong answer, because the straight-line guess is then exact, with nothing for it to
overestimate around. It's the combination of a scaled-up guess and a wall that fools the search,
not the weight alone.
Also in Strategy & computation: Braess's paradox →
← the cabinet · Thought Toys — a cabinet of explorable explanations. Exhibit 36.