A Note on Two Problems in Connexion with Graphs
Always extend the cheapest route found so far, and the shortest path to everywhere falls out.
How does your phone pick the single fastest road out of a country's worth of them — in a heartbeat, and without checking them all?
The big idea
Suppose you want the shortest route from your town to every other town on a map of roads. The brute-force way — try every possible route — explodes into impossibly many combinations. Dijkstra found a shortcut built on one disciplined habit: always extend the cheapest route you have found so far.
Start at home with a distance of zero, and mark every other town as “unknown distance.” Then repeatedly do the same small thing: among the towns you have not yet locked in, pick the one you can currently reach most cheaply, lock in that distance as final, and use it to update its neighbours. Because roads never have negative length, the cheapest town you can reach can't later turn out to be cheaper by some other way — so once you lock it in, you're done with it. Keep going and the shortest path to everywhere falls out, each one settled exactly once.
How it came about
In 1956 Edsger Dijkstra, a young programmer at Amsterdam's Mathematical Centre, needed a vivid demo for a new computer, the ARMAC. He picked a question anyone could grasp: what is the shortest way to drive from Rotterdam to Groningen? Sitting at a café terrace, tired from shopping with his fiancée and with no pencil and paper to hand, he worked the whole method out in his head in about twenty minutes.
He didn't publish it until 1959, in a three-page note that quietly solved two graph problems at once — the shortest path, and the minimum-length tree that connects every node. Dijkstra was careful about credit: the tree algorithm had been found years earlier by Jarník and by Prim, and others had circled the shortest-path idea too. What made his version last was how clean it was, and that he could say exactly why it always works.
Why it mattered
This little routine turned out to be one of the most-used algorithms ever written. Every time a navigation app draws your route, a delivery company plans its vans, or a packet of data hops across the internet, some descendant of Dijkstra's method is choosing the cheapest way through a network. It is fast enough to run on enormous maps and simple enough to prove correct — a rare and valuable combination.
A way to picture it
Picture pouring water into the pipe network at your home town, where every pipe's length is the travel time of a road. The water spreads outward and reaches each junction first by its shortest pipe — never by a longer detour, because the short way always arrives sooner. The moment water reaches a junction, you know the quickest time to it is fixed. Dijkstra's algorithm is exactly this flood, done one junction at a time: always fill the nearest dry junction next.
Where it sits
The 1950s gave computing its grammar: Shannon had quantified information, von Neumann had laid out the stored-program machine, and now Dijkstra showed how to make such machines reason efficiently about networks. His method is the ancestor of A* (the same idea, nudged toward a goal) and of the routing protocols that knit the internet together. In this Library it stands beside Shannon and von Neumann as one of the founding ideas of computer science — and beside the cryptography papers it shares a field with, since the network it routes over is the same one they keep secret.
Construct the tree of minimum total length between the n nodes.
Find the path of minimum total length between two given nodes