Thought Toys · Strategy & computation · Exhibit 26

Dijkstra's shortest path

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.

A grid from a start cell on the left to a goal on the right, crossed by a band of costly mountains with a cheap gap near the top; a cost-wavefront floods out from the start and the cheapest route is drawn in amber.

Raise the mountains and watch the route bend.

↳ your turn — drag the mountain cost to bend the route

What you're seeing

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.

The rule, exactly. Keep a tentative distance d to each node; repeatedly take the unsettled node of least d and relax its edges — d(v) ← min( d(v), d(u) + w(u,v) ) settling each node once. Verified in node (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).

Also in Strategy & computation: Nash equilibria →

All 23 in Strategy & computation
  1. 10The evolution of trust
  2. 23Sorting algorithms
  3. 24PageRank & the random surfer
  4. 25Huffman coding
  5. 26Dijkstra's shortest path — you are here
  6. 27Nash equilibria
  7. 33The learning-rate cliff
  8. 36A* pathfinding
  9. 37Braess's paradox
  10. 44Diffie–Hellman key exchange
  11. 45Preferential attachment
  12. 46Aliasing & the Nyquist limit
  13. 47The secretary problem
  14. 49Freeze too fast, stay stuck
  15. 51Cross one line, and its territory closes
  16. 56Catch one error, miss the next
  17. 57Why more processors stop helping
  18. 58Why a busy line explodes
  19. 59The set that's only sure when it says no
  20. 60The fit that memorizes instead of learns
  21. 61When the wire breaks, pick one
  22. 67Better at both, and still better off trading
  23. 69Everyone was consistent. The vote wasn't.

← the cabinet · Thought Toys — a cabinet of explorable explanations. Exhibit 26.