AlgoScope

Maximum Flow

algorithmadvancedTime O(V E^2)Space O(V^2)

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).

0/100/80/20/50/100/30/70/10012345

Push as much flow as possible from source 0 to sink 5. Each edge shows flow/capacity. Edmonds-Karp repeats: find the shortest path from 0 to 5 by BFS through edges with residual capacity, push the bottleneck along it, and stop when 5 cannot be reached.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. The path 0 > 1 > 3 > 5 has residual capacities 10, 5, 7. How much flow is pushed along it?

    • 5
    • 7
    • 10

    Answer: 5. The smallest residual capacity on the path limits it.

  2. The path 0 > 2 > 4 > 5 has residual capacities 8, 10, 10. How much flow is pushed along it?

    • 8
    • 10

    Answer: 8. The smallest residual capacity on the path limits it.

  3. The path 0 > 1 > 2 > 4 > 5 has residual capacities 5, 2, 2, 2. How much flow is pushed along it?

    • 2
    • 5

    Answer: 2. The smallest residual capacity on the path limits it.

How it runs, step by step

  1. Push as much flow as possible from source 0 to sink 5. Each edge shows flow/capacity. Edmonds-Karp repeats: find the shortest path from 0 to 5 by BFS through edges with residual capacity, push the bottleneck along it, and stop when 5 cannot be reached.

    Max flow from 0 to 5 over 6 vertices.

  2. BFS finds the shortest augmenting path 0 > 1 > 3 > 5, residual capacities 10, 5, 7. The bottleneck is 5.

    Augmenting path 0 to 1 to 3 to 5, bottleneck 5.

  3. Push 5 along the path: forward edges gain 5 of flow. Total flow 5. Now saturated: 1 > 3.

    Pushed 5, total 5.

  4. BFS finds the shortest augmenting path 0 > 2 > 4 > 5, residual capacities 8, 10, 10. The bottleneck is 8.

    Augmenting path 0 to 2 to 4 to 5, bottleneck 8.

  5. Push 8 along the path: forward edges gain 8 of flow. Total flow 13. Now saturated: 0 > 2.

    Pushed 8, total 13.

  6. BFS finds the shortest augmenting path 0 > 1 > 2 > 4 > 5, residual capacities 5, 2, 2, 2. The bottleneck is 2.

    Augmenting path 0 to 1 to 2 to 4 to 5, bottleneck 2.

  7. Push 2 along the path: forward edges gain 2 of flow. Total flow 15. Now saturated: 1 > 2, 2 > 4, 4 > 5.

    Pushed 2, total 15.

  8. The search from 0 reaches only {0, 1}: every edge leaving that set is saturated and no flow comes back into it to undo. No augmenting path is left, so the flow 15 is maximum.

    No augmenting path. Flow 15.

  9. Maximum flow 15 after 3 augmentations. Choosing the shortest path each time bounds the number of augmentations by O(V E), so Edmonds-Karp runs in O(V E^2) whatever the capacities.

    Maximum flow 15.

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.

Topics covered

Related

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