Modern engineering · Interactive model
The Route Finder
A city has tens of thousands of intersections, and your phone finds the fastest way across it before you've put it back in your pocket. It does not check most of them. The trick isn't a faster computer — it's refusing to look where the answer can't be. Guess how much of the map a smart search skips, then watch four searches cross the same city.
Guess first — commit before you look
Dijkstra's algorithm spreads outward in every direction until it bumps into the destination. A* adds one thing: the straight-line distance to the destination, as a hint about which way to look. Both return the fastest route — they just do different amounts of work to get there.
On the map below, Dijkstra visits — intersections. How many does A* visit to find the exact same route?
The search — same city, four strategies
Pick a strategy and run it. Blue is ground the search actually walked; green is the route it returns.
Make your call above first — then run it and see who was right.
Click the map to place the selected pin, or focus it and use the arrow keys. Right across town is the awkward case worth seeing: when the trip spans the whole known map there is barely anywhere left to prune, and even A* has to look at most of it — which is why real routers precompute instead.
| Strategy | Visited | Share of Dijkstra | Travel time | Route |
|---|---|---|---|---|
| Dijkstra | — | — | — | — |
| A* | — | — | — | — |
| Bidirectional | — | — | — | — |
| Greedy | — | — | — | — |
Read the map
Four searches, one road network — and only one of them is guessing.
Cheapest first, everywhere
Always expand the unvisited intersection you can reach most cheaply, then repeat. It cannot be beaten on the answer — but it has no idea where it's going, so it searches a circle around the start and finds the destination on the edge of it.
Cost so far, plus a hint
Rank each intersection by time already spent + straight-line time still to go. The hint bends the circle into a cone pointed at the destination. As long as the hint never over-estimates, the answer stays provably optimal — you just stop paying for the parts of the map that can't contain it.
Bidirectional search
Run two searches, one from each end, and stop when they touch. Two searches of half the radius cover far less ground than one full-radius search — on an open network, about half the area. This little map clips the circles at its edges, so the saving here is nearer a third; the effect is the one you see in every "Maps thinking" animation, where the blue roots grow toward each other.
Greedy: hint only
Chase whatever looks closest to the destination and ignore what the trip has cost so far. It visits almost nothing — and on the rush-hour map it will happily send you down a jammed arterial or to the wrong bridge. Speed you can't trust isn't speed. Turn on rush hour and compare its travel time to Dijkstra's.
Where this bites
The same move — prune with a cheap estimate — wearing different clothes.
The query planner
Your database doesn't try every way to join five tables. It estimates the cost of each plan from table statistics and searches only the promising ones. When the statistics go stale the estimate lies, the planner prunes the good plan, and a report that ran in a second takes ten minutes — the same failure as a bad heuristic.
Dispatch and delivery
Routing a fleet is this problem with an extra dimension — and the winners aren't the ones with the biggest servers. They're the ones with the best estimate of what a leg will cost, which is why live traffic and historical speed data are the actual moat, not the algorithm.
Screening a pile
Nobody interviews 800 applicants. You rank on a cheap proxy and look at the top of the list — a heuristic search. It's fast and it's often fine, but an over-confident proxy quietly prunes the best candidate, and you never find out, because you only ever see what the filter let through.
Search under an evaluation
Game engines and AI agents can't enumerate every future either. They expand the branches a scoring function likes and cut the rest. The intelligence sits in the estimate, not the exploring — which is why a better evaluation beats more compute more often than the reverse.
What the real thing does
Production routing goes further than this — in a direction worth knowing.
A continent-scale router doesn't run plain A* at request time. It precomputes: road networks barely change, so systems like contraction hierarchies spend hours offline building shortcut edges that let a query skip whole regions, turning a cross-country route into a few thousand steps. Live traffic, turn restrictions, road classes and your own preferences then re-weight the graph on the way past. The lesson survives the upgrade: the win comes from knowing where not to look — a heuristic buys that at query time, precomputation buys more of it in advance. This model uses a grid of a few hundred intersections and simple travel-time weights, so treat the counts as the shape of the effect, not a benchmark.
Dijkstra and A* return the same route. The difference is only how much of the map they had to rule out first — and that difference is the whole product.