A Good Guess
Three searches for the same route. One is careful, one is clever, and one is fast and wrong.
What it is
The same maze searched three ways, with the shaded region showing everywhere the search looked. Dijkstra spreads out in all directions. A* leans towards the goal. Greedy charges at it.
The table is the whole story.
How it works
Dijkstra always expands the cheapest-so-far node. A* expands the node with the lowest cost so far plus estimated cost remaining, and the estimate is the only difference between them. Set the estimate to zero and A* becomes Dijkstra exactly, which is how this page implements all three: one search function, three heuristics.
The estimate here is Manhattan distance, which on a four-connected grid of unit steps can never overestimate. With no walls it’s exactly the remaining cost, and walls only make the real cost longer.
Never overestimating is called admissibility, and it’s what guarantees A* still finds the shortest path. There’s a test that checks it directly, comparing the heuristic against the true remaining cost from every open cell on a random grid.
What surprised me
The size of the trade-off in both directions, measured over ten random mazes:
| search | nodes examined | shortest path? |
|---|---|---|
| Dijkstra | 1,573 | always |
| A* | 870 | always |
| greedy (4× overestimate) | 133 | never |
A* saves 45%, which I expected. The greedy version saves 92%, twelve times less work than Dijkstra, and in ten mazes out of ten it returned a path that wasn’t the shortest.
Ten out of ten is the part worth sitting with. I’d half expected inadmissibility to be a risk that mostly doesn’t bite, the kind of thing that goes wrong on adversarial inputs. It bites every single time on ordinary random mazes. The guarantee isn’t a formality protecting against rare cases, it’s the difference between an answer and a suggestion.
And the failure is invisible from inside. The greedy search returns a perfectly legal, connected, wall-avoiding path. Nothing about it looks wrong unless you already know the right answer, which is exactly the situation you’re in when you pick a heuristic because it’s fast.
What I would do next
Weighted A*, where the overestimate is tunable and the suboptimality is bounded. You can trade a guaranteed 10% worse path for most of the speed.