Maximum Flow
In short: A flow network is a set of pipes, each with a capacity, and the question is how much can move from a source to a sink at once. Edmonds-Karp answers it by repeatedly finding a shortest route with spare capacity (an augmenting path) and pushing the most it can along it. Every push opens a same-sized pipe running the other way — a residual edge — so a later path can undo part of an earlier commitment if that turns out to free up more overall. The algorithm stops when no augmenting path is left, after at most O(V·E) pushes, each costing an O(E) search: O(V·E²).
From matching to flow
Section 17's driver-and-job dispatch board was already a flow network, drawn differently. Give every driver one pipe of capacity 1 from a source, every licence a pipe of capacity 1, and every job one pipe of capacity 1 to a sink, and "the largest matching" and "the maximum flow" are the exact same number. The augmenting-path flip that moved dee into the van and pushed ana to the truck was already using a backward edge — the pipe that undid dee's job going to someone else's chain. This lesson writes that machinery out in full, for pipes that carry more than one unit at a time.
The residual graph
For every pipe a -> b with capacity c, keep two numbers: how much of c
is still free (the forward residual), and how much flow is currently
running through it, available to be taken back (the backward residual,
starting at 0). Pushing amount along the pipe does both at once:
Nobody built a pipe from axle back to dock. It exists purely as a bookkeeping trick: it is never bigger than the flow currently running forward, and using it is never "more" flow than was already committed — it is a way to change your mind.
Edmonds-Karp: BFS for a shortest augmenting path
Watch it find 5 units of capacity from depot to harbour in Meridian's depot network. The second path is the whole lesson — it has to use the residual edge the first path opened:
Every pipe carries a forward capacity. Pushing flow along one opens a same-sized reverse edge — the undo — even though no pipe was built backwards.
Meridian wants to know how much can move from depot to harbour right now. Every edge shows its full, untouched capacity. 6 nodes, 7 edges, directed. At depot.
In code
residual[u] holds every neighbour reachable by a positive-capacity
pipe in either direction — forward pipes and the reverse edges flow has
opened. BFS doesn't know or care which is which; it just follows whatever
has capacity left. That is exactly why the algorithm can undo a bad early
commitment without any special case in the code.
Why BFS, and why it's safe to undo
A greedy depth-first search can wander down a route that boxes itself in, the way first-come-first-served boxed in dee's driver assignment. BFS always finds a shortest augmenting path, and each one strictly cannot get shorter than the last (a short argument, not proved here) — so the number of augmentations is bounded by O(V·E), and each BFS costs O(E). Total: O(V·E²). Using a reverse edge never creates flow from nothing: it only ever reroutes flow that genuinely exists, which is why the final total is still a valid flow — conservation holds at every node, every step.
When the bottleneck is obvious
residual = {"a": {"b": 3}, "b": {"a": 0}}
push = 2
residual["a"]["b"] -= push
residual["b"]["a"] += push
print(residual)The bug that never undoes anything
Flow was pushed along s->a and a->t, but the reverse edges never grew to record it. Fix push_flow so pushing amount from u to v also adds amount to residual[v][u].
Quick practice
# s->a capacity 2, a->t capacity 5 — a two-pipe chain
caps_on_the_chain = [2, 5]
print(min(caps_on_the_chain))# s->a->t at capacity 3, and a completely separate s->b->t also at capacity 3
route1 = min(3, 3)
route2 = min(3, 3)
print(route1 + route2)How slow is O(V·E²), really
Each BFS costs O(E). Every augmentation saturates at least one edge, and a careful argument (not repeated here) bounds the number of augmentations at O(V·E), since an edge can become the bottleneck, get un-saturated by a backward edge, and become the bottleneck again — but only O(V) times each. On Meridian's full depot graph (a few hundred junctions, a few thousand pipes), that is comfortably fast for a nightly capacity check. For a live query against a much bigger network, the next lesson's algorithm cuts the exponent.
| Augmentations | Cost each | Total | |
|---|---|---|---|
| Edmonds-Karp | O(V·E) | O(E) | O(V·E²) |
❓ Cross-question: "If the first path I find already gets the full answer, do I still need the backward edges?" Yes — you don't know in advance whether you'll need one. The algorithm always opens them; most networks just never end up using them, the way the two separate routes above never did.
🎯 Your turn
Write push_volume(pipes, source, sink). pipes is a list of
[from, to, capacity]. Return the most volume that can move from source
to sink at once:
push_volume([["s", "a", 3], ["a", "t", 2]], "s", "t")→2
Hint: build the residual graph first (forward capacity, plus a reverse entry starting at 0), then repeat: BFS for a path with capacity left, push its bottleneck both ways, until BFS can't reach the sink.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Meridian's dispatcher is built. ✅