Graph theory on a road network: Dijkstra's shortest path from A to B with real alternatives, a minimum spanning tree, or Euler's one round of every road.
Graph theory: Dijkstra's shortest path (1956), Borůvka's spanning tree (1926) and Euler's bridges of Königsberg (1736)
Graph theory studies networks as nodes joined by edges, and it began with a walk. Königsberg's townspeople asked whether anyone could cross each of the Seven Bridges of Königsberg exactly once, and in 1736 Leonhard Euler showed why not: a walk over every edge once, an Eulerian path, must leave each node as often as it arrives, so every node needs an even number of edges.
Here the graph is a road network, with junctions as nodes and roads as weighted edges, each road's weight its length with a little traffic, so the quickest route is not always the straightest. Three classic algorithms run on it. Dijkstra's algorithm, which Edsger Dijkstra worked out in twenty minutes at a café in Amsterdam in 1956, solves the shortest path problem: settle the nearest unsettled junction, update its neighbours, repeat, so the search spreads out from A like a ripple until it reaches B. The alternative routes are found the way route planners offer choices: once a route is found its roads count as slower and the search runs again, keeping only routes that are genuinely different.
Borůvka's algorithm, from 1926, finds a minimum spanning tree, the cheapest set of roads that still joins every junction; Otakar Borůvka devised it to wire Moravia with electricity using the least cable, by letting every piece of the network take its cheapest link to another, all at once, until one tree remains.
The route inspection problem, or Chinese postman problem, posed by Kwan Mei-Ko in 1962, asks for the shortest round that drives every road at least once: the junctions with an odd number of roads are paired up, nearest first, and the roads between them doubled, after which Euler's round always exists, and Hierholzer's algorithm finds it. In motion each algorithm does its work.
Behind the mathematics
Dijkstra's algorithm for shortest paths, 1956
Dutch computer scientist who in 1956, in about twenty minutes at a café in Amsterdam, worked out the shortest-path algorithm that still guides route planners, and who went on to shape structured programming and concurrency.
The Seven Bridges of Königsberg and Eulerian paths, 1736
Swiss mathematician who in 1744 found the catenoid, the surface made by spinning a hanging chain, and showed it encloses the least area between two rings.
Borůvka's algorithm for minimum spanning trees, 1926
Czech mathematician who in 1926 gave the first algorithm for a minimum spanning tree, to find the cheapest electrical network for southern Moravia.
The Chinese postman (route inspection) problem, 1962
Chinese mathematician who in 1962, thinking about a postman's daily round, posed the problem of the shortest route that covers every street and gave the first method for it; it is now called the Chinese postman problem.
