The Last Mile.
Every map app, every router, every game's pathfinding runs some flavour of this. But you won't watch it. You'll drive it — lose to your own instincts, then meet the courier who never does.
Dijkstra's algorithm finds the shortest path from a starting point to every other point in a weighted graph — a network where each connection has a cost (here, minutes of traffic). Its one idea: always expand the cheapest-known point first, and the moment you reach a point that way, its shortest distance is locked in forever. That's it. It's how maps route you, how the internet routes packets, and how game characters find their way.
- Nodean intersection / point
- Edgea street between two nodes
- Weightthe cost to cross an edge
- Frontieropen nodes, cheapest-first (a priority queue)
- Relaxfound a cheaper route → lower a node's distance
- Settlelock a node — its distance is now final
Text version of the city map (for screen readers & keyboard)
What you just played, written down
You drove it, watched the flood, and predicted the next lock. Here's the same thing as an algorithm — it should read like subtitles to a movie you've already seen.
How the Dispatcher thinks — five steps
- Set distances. The start is 0; every other node is ∞ (unknown).
- Open the start. Put it in a priority queue keyed by best-known distance.
- Pop the cheapest. Take the open node with the smallest distance — call it current.
- Relax neighbours. For each street out of current, if reaching the neighbour through current is cheaper than its best-known distance, lower it.
- Settle & repeat. Lock current — its distance is now final — and loop until the queue empties (or you've settled the goal).
Because no street costs less than zero, the instant a node is popped as the cheapest open node, no other path could ever reach it more cheaply. So its distance is safe to lock. That single guarantee is the whole algorithm — and exactly the law you saw in the game.
The algorithm
function dijkstra(graph, start):
dist[start] = 0
for every other node v: dist[v] = ∞
pq = min-priority-queue seeded with (0, start)
while pq not empty:
(d, u) = pq.pop_min() # cheapest open node
if u is settled: continue
settle(u) # dist[u] is now final
for each edge (u → v, w):
if dist[u] + w < dist[v]: # relaxation
dist[v] = dist[u] + w
prev[v] = u
pq.push((dist[v], v))
return dist, prev # prev rebuilds the pathSolved by hand — the exact trace for the city above
Every lock in order, with the best-known distance at the moment it settled. This is precisely what the loop above does, run on the map you just played.
⚠ When it breaks
Dijkstra trusts that locking is final — which is only true with non-negative weights. Add a negative edge and a cheaper path can appear after a node is already settled, quietly corrupting the answer. (Go to Act 4 — Break it and make a street pay you: you'll create a negative cycle Dijkstra never notices.)
↔ Its cousins
Bellman-Ford handles negative edges (slower: O(V·E)). Add a goal-direction heuristic and Dijkstra becomes A*, which aims the flood as a beam instead of spreading everywhere. BFS is just Dijkstra when every weight is 1.
★ Where you've used it
Turn-by-turn navigation (Maps), internet routing (OSPF / IS-IS), NPC and unit pathfinding in games, network-latency planning, and plenty of "cheapest way from A to B" puzzles.