The encyclopedia · Software & IT · Technical decision · 1959–1970
Dijkstra's one ordered sweep made shortest-path routing a solved problem
A 1959 three-page note showed how to find shortest routes from one point to all others by always expanding the nearest unsettled node.
Mathematical Centre Amsterdam
the move
In the 1950s, finding shortest routes between cities, telephone exchanges or road junctions was a manual and combinatorial chore. Edsger Dijkstra wrote a three-page note in 1959 showing that the problem—shortest paths from one source to all nodes in a graph with nonnegative weights—has a simple exact solution.
The idea is to grow a settled region outward: at each step, take the unsettled node with the smallest current distance and mark it final, because any alternative route to it would have to pass through a node at least as far away already. Then update its neighbors. The sweep needs only a priority queue, so it runs in near-linear time.
What looks like a greedy trick is actually provably optimal for nonnegative weights, and the same ordered-expansion idea became the backbone of route planning in navigation systems, road networks, internet routing and logistics.
why it works
- Settling nodes in distance order guarantees each finalized distance is optimal, eliminating backtracking.
- The algorithm needs only one pass per node plus a priority queue, so it scales to real road and network graphs.
- It is easy to implement and verify, which is why it shipped inside navigation and routing products for decades.
- It solved a whole class of problems (single-source shortest paths) rather than one instance.
what transfers
A good algorithm often replaces repeated global search with one carefully ordered pass—process the easiest certainty first and the rest falls out.
what came after
Dijkstra's algorithm became one of the most taught and most used algorithms in computer science, a standard component of GPS navigation, network routing and logistics software. Later refinements (A*, bidirectional search, highway hierarchies) build directly on its ordered-expansion principle.
references
spotted an error? The archive wants to know.