Thought Toys · Computation & information · 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 Computation & information: The learning-rate cliff →

All 20 in Computation & information
  1. 101Noise sets a speed limit, not an accuracy limit.
  2. 111Any party of six hides a trio
  3. 120How one bit of ink makes a grey
  4. 125The ambulance that arrives sooner by going slower
  5. 131Every number is a sum of Fibonacci numbers
  6. 23Sorting algorithms
  7. 24PageRank & the random surfer
  8. 25Huffman coding
  9. 26Dijkstra's shortest path — you are here
  10. 33The learning-rate cliff
  11. 36A* pathfinding
  12. 44Diffie–Hellman key exchange
  13. 49Freeze too fast, stay stuck
  14. 56Catch one error, miss the next
  15. 57Why more processors stop helping
  16. 58Why a busy line explodes
  17. 59The set that's only sure when it says no
  18. 60The fit that memorizes instead of learns
  19. 61When the wire breaks, pick one
  20. 82Your computer can't hold one tenth

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