Thought Toys · Strategy & computation · Exhibit 26
The cheapest way across isn't the straightest. Dijkstra finds it by always reaching for the nearest-by-total-cost place it hasn't settled yet — so a wavefront of equal cost floods outward and bends around whatever is expensive. Raise the mountains and watch the best route abandon the straight line.
Find the cheapest way across
Raise the mountains and watch the route bend.
A little world of squares. Getting onto a normal square costs 1; the dark mountain band in the middle costs a lot more, except for a cheap pass near the top. We want the cheapest route from the start on the left to the goal on the right.
Dijkstra's idea is almost embarrassingly simple: keep a running cheapest-cost-so-far to every square, and each step, settle the cheapest unsettled square and update its neighbours. Because it always settles the nearest frontier first, the settled region grows as a set of equal-cost contours — the teal wavefront you see flooding out. When that wavefront first reaches the goal, the cheapest route is locked in (it can stop right there). Trace the amber line back and you've got the answer.
Now the dial. With flat ground (1×) every step costs the same, so the route with the fewest steps — the straight line — is also the cheapest; Dijkstra and plain "go straight" agree. Raise the mountain cost and, past roughly 3×, the cheapest route gives up on the straight line and detours through the pass: more steps, but cheaper. Hit Compare fewest-hops to see the naive straight route plough through the mountains and overpay. That split — fewest steps is no longer cheapest — is the whole reason Dijkstra orders its search by cost, not by hops. It's the engine inside every routing app finding the fast way, not the short way.
improve/verify/26-dijkstra.js):
Dijkstra's distances match an independent Bellman–Ford reference on the scene and on 40 random weighted
grids; the recovered route's cost equals the settled distance; at 1× the cheapest cost (21) equals the
straight fewest-hops route, while at 25× the cheapest detour (29) beats the straight route (117) — so the
shortest path really does bend away from the straight line. Counter-example: a single
negative edge breaks Dijkstra — its "settle the nearest, once" rule locks in a node before a cheaper
detour is found, returning 5 where the true shortest is 2 — which is exactly why it demands non-negative weights
(and why Bellman–Ford exists).
← the cabinet · Thought Toys — a cabinet of explorable explanations. Exhibit 26.