Shortest Paths and Network Flows

Ask your phone for directions and, in a heartbeat, it sifts millions of road segments to hand you the quickest way there. Stream a video and the internet quietly routes your packets through whichever pipes have room to spare. Both jobs live on the same object: a graph whose edges carry numbers. When the number on an edge means a cost — kilometres, minutes, dollars — we hunt the shortest path. When it means a capacity — cars per minute, gigabits per second, litres per hour — we hunt the maximum flow.

These are the two great optimisation problems on weighted graphs, and this page teaches them as one story: put a number on every edge, then either add the numbers along a route (and minimise), or squeeze stuff through them (and maximise). We will meet Dijkstra's algorithm for the first and the beautiful max-flow min-cut theorem for the second.

Part 1 — Shortest paths: cheapest route from a source

Give every edge a non-negative weight (a distance or cost). The length of a route is just the sum of the weights of the edges you walk. The shortest-path problem asks: starting from one source vertex, what is the cheapest total cost to reach every other vertex — and by which route?

The trap is that the shortest path is often not the one with the fewest edges. A single long edge can cost more than a three-edge detour of small ones. So we cannot just count hops; we must add up weights and compare. The clever bit is doing this without checking every route by hand — there can be astronomically many.

Dijkstra's algorithm: greedily settle the nearest

Edsger Dijkstra's idea is a greedy one, and it is gorgeous. Keep a running best guess of the distance to every vertex (the source is 0, everything else starts at \infty). Then repeat two moves:

  1. Settle the unsettled vertex with the smallest current distance. Because all weights are non-negative, nothing can ever make it cheaper later — so this distance is now final.
  2. Relax each edge u \to v leaving it: if going through u reaches v more cheaply than v's current guess, lower the guess.

Relaxation is the whole engine — one line that keeps only the best route found so far:

\text{if } \operatorname{dist}(u) + w(u,v) < \operatorname{dist}(v), \quad \text{set } \operatorname{dist}(v) = \operatorname{dist}(u) + w(u,v).

Keep going until every vertex is settled. The settled distances are the shortest distances, and the edges that "won" each relaxation form a shortest-path tree — a spanning tree of cheapest routes rooted at the source.

// Dijkstra: cheapest distance from `source` to every vertex. // graph: vertex -> list of [neighbour, edgeWeight] with weights >= 0. function dijkstra(graph: Map<string, [string, number][]>, source: string) { const dist = new Map<string, number>(); for (const v of graph.keys()) dist.set(v, Infinity); dist.set(source, 0); const unsettled = new Set(graph.keys()); while (unsettled.size > 0) { // 1. Settle the nearest unsettled vertex — its distance is now final. let u = ""; let best = Infinity; for (const v of unsettled) { if (dist.get(v)! < best) { best = dist.get(v)!; u = v; } } unsettled.delete(u); // 2. Relax every edge leaving u. for (const [v, w] of graph.get(u)!) { const alt = dist.get(u)! + w; if (alt < dist.get(v)!) dist.set(v, alt); // a cheaper route to v } } return dist; }

Walk it through: source A

Here is a small weighted graph. We run Dijkstra from A. Settle the nearest each time and relax:

Final distances from A: A{=}0,\ B{=}2,\ C{=}4,\ D{=}5,\ E{=}6,\ F{=}9. Step through the figure to see the shortest-path tree light up, then the single cheapest route to F.

Dijkstra dreamed the algorithm up in 1956 — reportedly in about twenty minutes, over coffee with his fiancée, while trying to show off the power of a new computer by finding the shortest drive between two Dutch cities. He published it in a three-page paper. Today essentially the same idea (souped up with a priority queue, and "A*", which adds a straight-line hint toward the goal) is what powers route planners, the internet's link-state routing protocols, and even the AI that finds a path across a video-game map. A twenty-minute idea now steers a billion journeys a day.

Plain Dijkstra breaks on negative edge weights. Its whole correctness rests on one promise: once you settle the nearest vertex, no cheaper route can appear later. A negative edge shatters that promise — a long path could suddenly get cheaper by dipping through a -4 edge after you have already "finalised" a vertex. So Dijkstra can settle a vertex too early and return a wrong distance.

If weights can be negative, use Bellman–Ford instead (it relaxes every edge repeatedly, and even detects negative cycles). And do not confuse the two problems: a shortest-path algorithm minimises a sum along one route — it is not the same machinery as the flow problem below, where the goal is to maximise throughput.

Part 2 — Network flows: how much can you push through?

Now change what the numbers mean. Take a directed network with a source s and a sink t. Each edge has a capacity — the maximum it can carry (think pipe width, or a road's cars-per-minute). A flow assigns an amount to each edge obeying two rules:

The maximum-flow problem asks: what is the greatest total amount you can send from s to t at once? Water from a reservoir, packets across the internet, oil down a pipe network — same question every time.

The bottleneck rules everything

Look at this network. The source can gush 5 + 5 = 10 into the outer pipes, and the pipe to the sink is a roomy 9 — but everything must squeeze through the two narrow edges into c, worth only 2 + 2 = 4 together. So the maximum flow is 4, not 9 or 10. The narrowest part of the system, not the widest, sets the limit.

A cut is any way of splitting the vertices into an s-side and a t-side; its capacity is the total capacity of the edges crossing from the s-side to the t-side. Every cut is a wall the flow must pass through, so no flow can beat the smallest cut.

Max-flow min-cut: the two problems are secretly equal

Here is the punchline, one of the jewels of combinatorial optimisation. That obvious ceiling — "flow can't exceed any cut" — is actually always tight. You can always find a flow that reaches the smallest cut exactly.

This turns a maximisation (find the biggest flow) and a minimisation (find the cheapest wall) into two sides of one coin — proved by finding "augmenting paths" until none remain, the Ford–Fulkerson method. It is also wonderfully practical: it certifies an answer. If you produce a flow of value 4 and a cut of capacity 4, each one proves the other is optimal — no further search needed.

Flow networks hide in surprising places. Want to assign n workers to n jobs so as many people as possible get a job they can do? Build a network: a source s into every worker (capacity 1), an edge from a worker to each job they're able to do (capacity 1), and every job into a sink t (capacity 1). The maximum flow is exactly the largest possible matching. The same trick schedules airline crews, pairs organ donors to recipients, and assigns students to schools — all "just" max-flow in disguise.