Maximum Flow
Think of the edges as pipes with capacities and ask how much can be pumped from the source to the sink. The trick is the residual graph: an edge with room left can still carry more, and an edge already carrying flow can be walked backwards to undo some of it. Any path from source to sink through residual edges lets you push the smallest residual along it, and when no such path is left the flow is maximum. The set of vertices still reachable at that point gives away the bottleneck: the edges leaving it are all full and add up to exactly the flow, which is the max-flow min-cut theorem. Bipartite matching is the same algorithm on a network where every capacity is one. Dinic's algorithm pays for one BFS and then reuses it: the BFS labels every vertex with its distance from the source, only edges that climb exactly one level are used, and paths are pushed through that level graph until none is left. Each phase makes the shortest path strictly longer, so there are at most V phases and the total is O(V^2 E).
Push as much flow as possible from source 0 to sink 5 with Dinic's algorithm. A phase starts with a BFS that labels every vertex with its distance from 0 through edges that still have room; the number on each vertex is that level. Only edges that go up exactly one level are used for the phase, and paths are pushed through them until none is left, a blocking flow. Then the levels are rebuilt. Each phase makes the shortest path strictly longer, so there are at most V phases.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.
Which edges may a path use during this phase?
Answer: Only edges that go up exactly one level. Only edges from level L to level L + 1: that keeps every path a shortest path, and it is why the phase count is bounded by V.
The path 0 > 1 > 3 > 5 has residual capacities 16, 12, 20. How much is pushed?
Answer: 12. The smallest residual capacity on the path limits it.
The path 0 > 2 > 4 > 5 has residual capacities 13, 14, 4. How much is pushed?
Answer: 4. The smallest residual capacity on the path limits it.
Which edges may a path use during this phase?
Answer: Only edges that go up exactly one level. Only edges from level L to level L + 1: that keeps every path a shortest path, and it is why the phase count is bounded by V.
The path 0 > 2 > 4 > 3 > 5 has residual capacities 9, 10, 7, 8. How much is pushed?
Answer: 7. The smallest residual capacity on the path limits it.
How it runs, step by step
Push as much flow as possible from source 0 to sink 5 with Dinic's algorithm. A phase starts with a BFS that labels every vertex with its distance from 0 through edges that still have room; the number on each vertex is that level. Only edges that go up exactly one level are used for the phase, and paths are pushed through them until none is left, a blocking flow. Then the levels are rebuilt. Each phase makes the shortest path strictly longer, so there are at most V phases.
Dinic's algorithm from 0 to 5 over 6 vertices.
Phase 1: BFS levels 0 at 0, 1 at 1, 2 at 1, 3 at 2, 4 at 2, 5 at 3; 5 is at level 3, so every shortest augmenting path has 3 edges. The highlighted edges are the level graph: residual edges from a level to the next. Everything else is ignored until the phase ends.
Phase 1, sink at level 3.
A path through the level graph: 0 > 1 > 3 > 5, residual capacities 16, 12, 20. The bottleneck is 12.
Path 0 to 1 to 3 to 5, bottleneck 12.
Push 12: total flow 12. Now saturated: 1 > 3, and it drops out of the level graph.
Pushed 12, total 12.
A path through the level graph: 0 > 2 > 4 > 5, residual capacities 13, 14, 4. The bottleneck is 4.
Path 0 to 2 to 4 to 5, bottleneck 4.
Push 4: total flow 16. Now saturated: 4 > 5, and it drops out of the level graph.
Pushed 4, total 16.
No path from 0 to 5 is left inside this level graph: a blocking flow. Every shortest path of length 3 is now saturated somewhere, so the next BFS will find 5 strictly further away, or not at all. Rebuild the levels.
Blocking flow reached; phase 1 over.
Phase 2: BFS levels 0 at 0, 1 at 1, 2 at 1, 4 at 2, 3 at 3, 5 at 4; 5 is at level 4, so every shortest augmenting path has 4 edges. The highlighted edges are the level graph: residual edges from a level to the next. Everything else is ignored until the phase ends.
Phase 2, sink at level 4.
A path through the level graph: 0 > 2 > 4 > 3 > 5, residual capacities 9, 10, 7, 8. The bottleneck is 7.
Path 0 to 2 to 4 to 3 to 5, bottleneck 7.
Push 7: total flow 23. Now saturated: 4 > 3, and it drops out of the level graph.
Pushed 7, total 23.
No path from 0 to 5 is left inside this level graph: a blocking flow. Every shortest path of length 4 is now saturated somewhere, so the next BFS will find 5 strictly further away, or not at all. Rebuild the levels.
Blocking flow reached; phase 2 over.
The BFS from 0 reaches only {0, 1, 2, 4} and never 5: every edge out of that set is saturated. No level graph contains 5, so the flow 23 is maximum.
Sink unreachable. Flow 23.
Maximum flow 23 after 2 phases and 3 augmentations. Each phase costs O(V E) for its blocking flow and the sink's level rises every phase, so Dinic runs in O(V^2 E): the level graph is what lets one BFS serve many paths, where Edmonds-Karp pays a BFS per path. On unit-capacity networks such as matchings it is O(E sqrt V).
Maximum flow 23.
Remember
- Residual capacity is cap - flow forwards and flow backwards; a backward step on the path undoes flow that turned out to be in the way.
- Push the smallest residual on the path, repeat until the sink is unreachable; BFS paths (Edmonds-Karp) keep the number of rounds polynomial.
- Max flow equals min cut: the vertices still reachable at the end are S, and every edge from S to T is saturated.
What the words mean
- Maximum Flow
- The most that can be sent from source to sink; grows by augmenting paths in the residual graph until none is left.
Where this is used
GraphicsGrabCut selecting a foreground object
Cutting an object out of a photo is posed as a network: every pixel is a vertex, its source edge weighted by how much it matches a learned foreground colour model, its sink edge by how much it matches the background, and edges to neighbouring pixels weighted by how similar those pixels are. The min cut is then the cheapest place to slice, which is exactly a boundary that follows the colour evidence while refusing to cut through a smooth region, so the edge hugs the object instead of scattering into speckle. OpenCV's cv::grabCut runs this directly, with an internal GCGraph::maxFlow that is a Boykov-Kolmogorov augmenting-path solver tuned for grid graphs.
NetworkingCrossbar scheduling inside a router
An input-queued switch fabric can connect each input to at most one output per time slot, so every slot needs a maximum matching between inputs holding cells and the outputs those cells want. That is this algorithm on a unit-capacity network, and integrality is what makes the answer usable: with every capacity one, the maximum flow is literally a set of edges rather than a fractional split. A real fabric has tens of nanoseconds to decide, far too little for an exact solve, so hardware runs iterative round-robin approximations such as McKeown's iSLIP (the ESLIP variant shipped in the Cisco 12000 fabric) and measures itself against the exact matching.
Developer toolsSimpleMaxFlow in Google OR-Tools
You hand it arcs with capacities and it returns the flow, plus GetSourceSideMinCut for the S side - because for most callers the cut is the real answer, naming which links are the bottleneck rather than just how much fits. It is a push-relabel implementation rather than augmenting paths, since on dense networks shoving excess between neighbours beats rebuilding an entire source-to-sink path every round. NetworkX's maximum_flow and the Boost Graph Library's boykov_kolmogorov_max_flow fill the same slot in other stacks.
OperationsChoosing which blocks of an open pit to mine
The ore body is cut into blocks, each worth money or costing money to remove, and a block can only be taken once everything above it has been taken. Hang the profitable blocks off the source, the costly ones off the sink, and give every precedence relation an infinite-capacity edge: the infinite edges guarantee no cut can cross a precedence, so the min cut is forced to pick the most profitable set that is actually diggable. Lerchs and Grossmann posed the ultimate pit as a maximum closure in 1965 and solved it with a graph algorithm of their own; Picard's 1976 result is the reduction that turns any maximum closure into a minimum cut, which is what lets a flow solver answer it. The same reduction is project selection - choose the subset of projects whose profit beats the shared equipment they all need.
Why it works this way
Why undoing earlier flow is not cheating
Take four vertices with every capacity one: s->a, s->b, a->b, a->t, b->t. Route s->a->b->t first and you have used the middle edge, and a greedy router that can only move forwards is now stuck at one unit. The backward residual edge b->a is what rescues it: the path s->b->a->t walks that edge backwards, cancelling the unit on a->b and rerouting it, and the total comes out at two. This is why the algorithm never has to choose paths wisely - every commitment it makes can be taken back by a later path.
Why BFS paths, and what goes wrong without them
Ford-Fulkerson allows any augmenting path, and a bad choice is ruinous: in the network with s->a and s->b at capacity 1000, a->t and b->t at capacity 1000 and a single a->b of capacity 1, a DFS that keeps zig-zagging through that middle edge moves one unit per round and needs 2000 rounds. With integer capacities each round still adds at least one, so it does terminate; with irrational capacities it can run forever and converge to something below the true maximum. BFS (Edmonds-Karp) always augments along a shortest path, and that alone caps the rounds at O(V E) no matter how large the capacities are.
A capacity matrix quietly breaks on antiparallel and parallel edges
cap[u][v] stores one number per ordered pair, and the whole residual trick leans on flow[v][u] == -flow[u][v], so the reverse direction is already spoken for as the undo channel. If the input genuinely contains both u->v and v->u, the two tangle: pushing flow on u->v shows up as extra room on v->u, and the solver will happily use a real pipe as if it were an undo. Two parallel u->v edges have the same problem and must be summed into one capacity. The standard fix is an edge list where each edge sits next to its reverse twin (index i and i xor 1), so an antiparallel pair is simply two independent edges with two independent twins.
Dinic only hits O(V^2 E) if a dead edge is never retried
Levels are fixed for the whole phase, so an edge that is saturated or leads into a dead end cannot become useful again until the next BFS. The DFS must therefore remember, per vertex, how far into that vertex's adjacency list it already walked and resume from there - the current-arc pointer. Without it the search rescans the same hopeless edges on every path and the blocking flow costs far more than the O(V E) per phase the bound assumes. On unit-capacity networks such as bipartite matching the same code drops to O(E sqrt(V)), which is what Hopcroft-Karp does.
Read more
- Maximum flow problemWikipedia
- Max-flow min-cut theoremWikipedia
- Maximum flow - Ford-Fulkerson and Edmonds-Karpcp-algorithms
- Maximum flow - Dinic's algorithmcp-algorithms
- Download SpeedCSES 1694 · cses.fi