Networks, 1956

A Demo for a New Computer

The Mathematical Centre in Amsterdam was about to unveil its second machine.

In 1956 the Mathematical Centre in Amsterdam (today called the CWI) was preparing the public unveiling of ARMAC, its second computer. ARMAC had magnetic-core memory, vacuum tubes, and a clock rate measured in microseconds. The staff wanted to demonstrate it to an audience of scientists, businessmen, and journalists, most of whom had never seen a computer before.

The demonstration needed a problem the audience could follow. Not a differential equation. Not a cryptographic cipher. Something concrete, something familiar. Edsger Dijkstra, a 26-year-old programmer at the Centre, was assigned to come up with it.

He chose a question that anyone driving in the Netherlands could understand: given a map of the 64 largest Dutch cities, what is the shortest road route between any two of them? The audience would call out a pair; the computer would answer in seconds.

“What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city? It is the algorithm for the shortest path, which I designed in about twenty minutes.”
Edsger Dijkstra, EWD 1166: From my Life

Dijkstra was out shopping in Amsterdam with his fiancée Maria Debets. They stopped at a café terrace on the Leidseplein for coffee. He had no pencil. No paper. In the twenty minutes before the shops reopened, he worked out the algorithm in his head. He later said the absence of pencil and paper almost forced him to avoid unnecessary complications.

The Problem, Precisely

A weighted graph, a source, a question about the cheapest way to everywhere else.

Give every edge a non-negative number. On a road map, the number is a distance. On a telephone network, it is a cost. On the internet, it is a latency. The graph with numbers attached is a weighted graph.

Pick a source node $s$ . The single-source shortest path problem asks: for every other node $v$ , what is the minimum total weight of any path from $s$ to $v$ , and what is a path achieving that minimum?

The brute-force answer is to enumerate every possible path. On a graph with $n$ nodes that can be exponentially many paths. Even on ten nodes it is intractable by hand. In 1956 the bottleneck was not that the problem was hard to state; it was that nobody had a good algorithm.

Why non-negative weights?

Dijkstra's method is greedy: once it decides a node's distance is final, it never revisits the decision. A negative edge could retroactively shorten a path through an already-settled node, which would break the guarantee. For graphs with negative weights you need Bellman-Ford (1958) instead. Road distances are always non-negative, which is why the ARMAC demo worked.

The Insight: Grow the Shortest-Path Tree

Settle the nearest unsettled node. Repeat until the graph is settled.

Dijkstra's idea: process nodes in order of their true distance from the source. Keep a running tentative distance to every node, starting at 0 for the source and $\infty$ for everyone else. At each step, pick the unsettled node with the smallest tentative distance, mark it as settled, and for each of its neighbours check whether going through the newly-settled node improves their tentative distance. Repeat.

The key claim: when a node becomes settled, its tentative distance is already correct. No later relaxation through any other settled node can shorten it, because all other settled nodes have smaller or equal distance, and the edges we have not yet crossed are non-negative. This is the invariant the greedy choice preserves.

Try it on a map. Pick a source (click a city). Pick a target (shift-click). The gold edges show the current shortest path. Drag the weights up or down and watch the path rearrange itself.

Dutch Roads: Shortest Path

Click a city to set the source. Shift-click to set the target. Click an edge label to add 10 km; shift-click to remove 10 km.

Shortest path

Rotterdam → Groningen

290 km

Rotterdam → Utrecht → Arnhem → Zwolle → Groningen

Distance from Rotterdam

Amsterdam90 km

Haarlem70 km

Utrecht60 km

The Hague25 km

Arnhem125 km

Zwolle190 km

Groningen290 km

Eindhoven110 km

Maastricht195 km

Notice how the shortest path is rarely the fewest-edge path. The two-hop route is often worse than a three-hop route. This is why BFS is not enough: BFS is correct only on unweighted graphs.

The Algorithm, Step by Step

Watch the frontier expand. Every extraction settles one node.

Below is the same Dutch road graph, with Rotterdam fixed as the source. Step through the algorithm one extraction at a time. Gold nodes are settled: their distance is final. Blue nodes are on the frontier: reached, but with only a tentative distance. Numbers below each city are tentative distances in kilometres; $\infty$ means not yet reached.

Dijkstra, Step by Step

Gold nodes are settled. Blue nodes are on the frontier. The current node is highlighted with a thicker ring.

Step 0 of 10

Initial state. The source is at distance 0. All other nodes are at distance ∞.

Frontier

Rotterdam0 km

Correctness

When the node $u$ is extracted from the frontier, its tentative distance $d [u]$ equals the true shortest-path distance from $s$ to $u$ .

In plain English: the moment Dijkstra reaches into the frontier and pulls out whichever node has the smallest tentative number attached to it, that number is already the truth. It is the real shortest distance from the source. No later discovery, no cleverer path found three iterations from now, will ever shorten it. Once a node is marked settled, it stays settled forever. This is the whole reason the algorithm is fast: each node is touched once, its answer recorded, and never revisited. Greedy and correct at the same time, which is a rare combination.

Why is it true? Here is the idea, and then the symbols. Imagine there is a secretly-better path to $u$ that Dijkstra does not yet know about. That path has to leave the settled region somewhere, because the source is settled and $u$ is not. The first node it steps out onto is some frontier node $y$ . But by the greedy rule, Dijkstra picked $u$ precisely because $u$ had a smaller tentative distance than every other frontier node, including $y$ . So the supposedly shorter path through $y$ cannot actually be shorter. Contradiction. The tentative distance was the truth all along.

Proof sketch. When $u$ is extracted, consider any path $P$ from $s$ to $u$ . Walk along $P$ and find the first node $y$ that is still on the frontier. The prefix of $P$ up to $y$ is already the shortest path to $y$ (by induction on settled nodes), so $d [y] \leq length (P)$ . But we chose $u$ , not $y$ , which means $d [u] \leq d [y] \leq length (P)$ . Since $P$ was arbitrary, $d [u]$ is at most the true shortest distance. It is also at least that distance, because $d [u]$ is the length of some path. So they are equal.

The complexity, with a binary heap as the priority queue, is $O ((V + E) lo g V)$ : every edge is relaxed at most once, every relaxation may trigger a heap push, and every node is extracted once. Fibonacci heaps bring it down to $O (E + V lo g V)$ , but in practice binary heaps win on cache behaviour.

To get a feel for what that bound means, picture a road graph with a million intersections and three million road segments. The brute-force "try every path" approach is astronomically hopeless, doubly-exponential in the worst case. Dijkstra on the same graph is a few tens of millions of basic operations, finishing in well under a second on any modern laptop. That is the gap between a problem that is trivial to state and a problem that is tractable to solve, and it is the gap the world had to wait twelve years for someone to close.

Why the World Had to Wait

Twelve years before ARMAC, the Allies had a logistics problem they would have loved to hand to Dijkstra.

In the summer of 1944, the Allied invasion of northern France depended on moving ammunition, fuel, and food from the Normandy beaches to armies racing east toward Germany. The Red Ball Express was the answer: a round-the-clock truck convoy system running reserved two-lane highways, at one point delivering over twelve thousand tons of supplies per day. The question of which roads to reserve, in what order, with what priority, is a shortest-path problem in all but name.

But no one in 1944 could call it that. The word graph in the modern combinatorial sense was known only to a small academic community. The first textbook on graph theory (Dénes König's) had been published in 1936. Linear programming, the technique that would let George Dantzig formalise supply logistics, would not exist until 1947. Operations Research teams on both sides of the Atlantic did extraordinary work by combining hand calculation, nomograms, and sheer intuition. What they did not have was an algorithm that turned a road network into an answer.

The gap between problem that mattered and algorithm that solves it was twelve years. That gap is typical of how graph theory has entered the world. The abstraction arrives first; the infrastructure that needs it arrives later; the algorithm that bridges them arrives later still. Euler gave us the language in 1736. The war gave us the motivation in 1944. Dijkstra, in 1956, closed the loop over a cup of coffee.

A common error

Popular accounts sometimes claim Allied Operations Research teams used max-flow or shortest-path algorithms during the war. They did not. Ford and Fulkerson's max-flow paper is from 1956; Dijkstra 1959; Bellman 1958; Dantzig's simplex method 1947. The OR work was real and decisive, but it used the tools available at the time: linear combinations of hand-computed tables, priority rules, and a lot of sleepless nights.

Python: Build It

A weighted graph in twenty lines. Dijkstra in fifteen.

Part A: A weighted graph

An adjacency list of (neighbour, weight) tuples. Negative weights are rejected at insert time, so the algorithm below can trust its input.

weighted.py Notebook 07

from collections import defaultdict
from dataclasses import dataclass, field

@dataclass
class WeightedGraph:
    """Undirected graph with non-negative edge weights."""
    _adj: dict[str, list[tuple[str, float]]] = field(
        default_factory=lambda: defaultdict(list)
    )

    def add_edge(self, u: str, v: str, weight: float) -> None:
        if weight < 0:
            raise ValueError(f"Negative weight {weight} not allowed.")
        self._adj[u].append((v, weight))
        self._adj[v].append((u, weight))

    def neighbours(self, node: str) -> list[tuple[str, float]]:
        return list(self._adj[node])

    @property
    def nodes(self) -> list[str]:
        return list(self._adj.keys())

Part B: Dijkstra's algorithm

A binary-heap priority queue keeps the frontier ordered by tentative distance. The “stale entry” check is what lets us push duplicate entries when we relax an edge, without needing a decrease-key operation.

dijkstra.py Notebook 07

import heapq
import math

def dijkstra(g: WeightedGraph, source: str):
    """Return (distances, predecessors) from source to every node."""
    distances = {n: math.inf for n in g.nodes}
    predecessors = {n: None for n in g.nodes}
    distances[source] = 0.0

    frontier = [(0.0, source)]                  # min-heap by distance
    while frontier:
        d, u = heapq.heappop(frontier)
        if d > distances[u]:                    # stale entry
            continue
        for v, w in g.neighbours(u):
            alt = d + w
            if alt < distances[v]:              # relaxation
                distances[v] = alt
                predecessors[v] = u
                heapq.heappush(frontier, (alt, v))

    return distances, predecessors

📓

Notebook 07: Dijkstra and the Dutch cities

Build the Dutch road graph. Run Dijkstra from Rotterdam. Recover a path from the predecessor map. Then watch what happens when you slip a negative edge into the graph, and why that is the boundary of the algorithm.

notebooks/07_graph_theory_dijkstra.ipynb →

What Dijkstra's Three Pages Became

Every packet you send. Every route you drive. Every turn-by-turn direction.

Dijkstra published the algorithm in 1959 in Numerische Mathematik, three pages under the title A Note on Two Problems in Connexion with Graphs. It was not the paper he thought would matter. The ARMAC demo was a novelty item.

Within a decade, shortest-path computation had become the core primitive of network routing. When the ARPANET came online in 1969 its routers computed shortest paths between Interface Message Processors. The OSPF protocol that routes much of the modern internet's backbone traffic is Dijkstra running inside every router, recomputing a shortest-path tree each time the network topology changes. The Bellman-Ford variant runs in every BGP-speaking router when negative weights (or path attributes that can behave like them) matter.

Google Maps, Waze, OpenStreetMap routing, the navigation screen in a modern car, the path a logistics algorithm picks to deliver a package: all descendants of those twenty minutes on the Leidseplein.

Flow and cuts

Ford and Fulkerson, max-flow / min-cut, and the Cold War rail study that motivated it.

Then

Random walks

PageRank built Google this way. Modern LLMs retrieve knowledge this way.

Eventually

Four algorithms

One insight from 1736 that made all of them thinkable.