How does a map app find the quickest way home? Behind the blue line is a graph: places are dots, roads are lines, and each road has a length. The task is to find the shortest chain of roads between two places. In 1959 Edsger Dijkstra published a three page note that solves it with a method so natural that we still teach it today.
His note, only three pages, treats two problems on a network of points joined by branches of known length. The first is to connect all the points with the least total length of branches. The second is to find the shortest path between two given points. The second one made him famous, and it is the one we follow here.
Dijkstra's method finds shortest paths by settling nodes in order of distance. Keep the best known distance to every node. Repeatedly take the closest node you have not finished, lock in its distance, and check whether it offers a shorter way to its neighbors. It works because branch lengths are never negative.
Three groups of nodes
Dijkstra describes the work with three sets of nodes. Start by choosing the node P you travel from.
- Set A: nodes whose shortest path from P is already known. Only P is here at the start.
- Set B: nodes joined by a branch to some node of A, so we have a route to them, but maybe not yet the shortest.
- Set C: every other node.
Each round has two steps. First, look at the branches from the node that just joined A. If one gives a shorter route to a node in B, or reaches a node in C for the first time, record it. Second, pick the node in B with the smallest distance and move it into A.
