Dinic, Level Graphs & Scaling
In short: Edmonds-Karp finds one shortest augmenting path, pushes it, and throws its BFS away. Dinic's algorithm keeps the BFS: it labels every node with its distance from the source (a level graph), then runs a single DFS that saturates every shortest route the level graph allows — a blocking flow — before rebuilding. Each phase strictly grows the sink's level, so there are at most V phases, and a phase with E edges costs O(V·E) to block, for a total of O(V²·E). On a network where several shortest routes don't share a node, one phase does the work Edmonds-Karp needed several separate searches for.
Same question, a wider network
Meridian's depot network from the last two lessons has only one route of each length, so Edmonds-Karp and Dinic take the same number of rounds on it. Widen it — add a second depot-fed branch through mill, and a longer one through port and relay — and the difference shows up immediately:
dock's and mill's routes are both length 2 and share no node. port's route is length 3. One phase settles the two short routes together.
BFS labels every node with its distance from depot. harbour is distance 2 — reachable via dock or mill — and relay, at distance 2, is still one hop short of harbour. 6 nodes, 7 edges, directed. depot: 0, dock: 1, mill: 1, port: 1, harbour: 2.
Why a phase can't repeat work
A blocking flow only ever follows an edge from level k to level k+1, so
no path within a phase revisits a node — the level graph is a DAG by
construction. Once a node's outgoing level-edges are all explored and dead,
the DFS never looks at it again this phase, because each node keeps its
own iterator instead of restarting from the top:
dead_end gets visited once, finds nothing, and it["s"] has already moved
past it — a second call to dfs("s", ...) within the same phase picks up
it["s"] where it left off, at a, never looking at dead_end again. That
is what makes a whole phase cost O(V·E) instead of O(V·E) per path.
In code
A residual edge opened by one phase is still just an edge: it gets its own level like anything else next phase, and can carry flow backward exactly the way Edmonds-Karp's could. Dinic doesn't trade away correctness for speed — it is still finding augmenting paths, just several at a time.
Quick practice
levels = {"s": 0, "a": 1, "b": 1, "t": 2}
# in the diamond network, is a->b a level-graph edge this phase?
is_level_edge = levels["b"] == levels["a"] + 1
print(is_level_edge)level_graph_only keeps a pipe whenever both ends have a level, but that lets the sideways a->b edge through. Fix it so a pipe only survives when level[b] == level[a] + 1, leaving s->a, a->t and b->t: 3 edges.
How much this actually saves
| Rounds | Cost per round | Total | |
|---|---|---|---|
| Edmonds-Karp | O(V·E) augmenting paths | O(E) BFS | O(V·E²) |
| Dinic | O(V) phases | O(V·E) blocking flow | O(V²·E) |
For a network with many more edges than nodes — Meridian's full depot
graph, where every junction has a handful of roads — E dominates, and
V²·E beats V·E² by roughly a factor of E/V. A network with 1,000
junctions and 4,000 roads is about 4× faster with Dinic; one with 1,000
junctions and 40,000 roads is 40× faster. The gap grows with how richly
connected the network is.
A further speed-up, capacity scaling, only looks for augmenting paths above a shrinking threshold (start near the largest capacity, halve it each round), which bounds the path count a different way and is worth knowing exists — Meridian's dispatcher doesn't need it at this scale.
❓ Cross-question: "Could a phase push zero flow and still count?" No — if sink has a level, the level graph has at least one path to it with positive residual capacity (that's how BFS found the level in the first place), so every phase that starts pushes something.
🎯 Your turn
Write push_volume_fast(pipes, source, sink) using Dinic's algorithm:
BFS for a level graph, DFS for a blocking flow that only steps from level
k to k+1, repeat until BFS can't reach sink:
push_volume_fast([["s", "a", 3], ["a", "t", 2]], "s", "t")→2
Hint: reuse each node's neighbour iterator across DFS calls within a phase, so a dead end found once is never re-explored that phase.
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. ✅