Maximum flow
Push as much as possible from a source to a sink through a network whose links have limited capacity.
- Complexity
- Polynomial time
- Used for
- Network bandwidth, Water distribution, Supply chains
- In this lab
- Edmonds–Karp, Ford–Fulkerson, Dinic, push–relabel
- Pipe width is capacity
- Flow
- Search tree
- Path or arc in focus
Augmenting paths, in order
Each row is one push. The bottleneck is the smallest spare capacity along the path.
| # | Path | Bottleneck | Total after |
|---|---|---|---|
| 1 | s → v1 → v3 → t | 12 | 12 |
| 2 | s → v2 → v4 → t | 4 | 16 |
| 3 | s → v2 → v4 → v3 → t | 7 | 23 |
Augmenting paths each algorithm needs
The three path-based algorithms reach the same maximum flow of 23, but differ in how many paths they push along. Push–relabel gets there with 13 pushes and 11 relabels instead.
The problem
A network of pipes, cables or roads connects a source s to a sink t. Every link has a capacity: how much can pass through it per unit of time. How much can you send from s to t in total, and along which links?
Bandwidth between two data centers, water from a reservoir to a city, goods from factories to a port: all are flow problems. The surprise is how many problems that don't look like pipes turn out to be max flow in disguise: assigning workers to jobs (bipartite matching), separating an object from the background of a photo (image segmentation by minimum cut), choosing profitable projects with prerequisites, or deciding whether a sports team can still mathematically win its league.
Formal model
Give every edge (u, v) a flow value f(u, v). A flow is valid when it respects two rules:
A cut splits the nodes into a side S containing s and a side containing t. Everything that reaches t must cross from S to the other side, so no flow can exceed the total capacity of the edges leaving S. The max-flow min-cut theorem says the bound is tight: the maximum flow equals the capacity of the smallest cut. In the lab, the last step shows that cut. It's the set of nodes the final search could still reach, and every edge leaving it is full.
Why this one is easy
Unlike the other four problems in this lab, maximum flow is solvable in polynomial time. It is a linear program, and a special one: when all capacities are integers there is always a maximum flow that uses whole numbers on every edge (the integrality theorem). That's what makes matching and assignment problems easy to solve through flows.
Notice the contrast. Knapsack, bin packing, scheduling and routing all hide an "all or nothing" decision: an item is packed or not, a job goes first or second. Flow can be split freely and still come out whole, and that difference is the boundary between easy and hard here.
Data structures
The residual graph
Every algorithm here works on the residual graph. Each edge (u, v) with capacity c and flow f becomes two arcs: a forward arc u → v with c − f spare, and a backward arc v → u that can carry up to f. Pushing along a backward arc means cancelling flow sent earlier, which lets the algorithm change its mind. Switch the lab's view to "Residual graph" to see both kinds of arc.
In code, edges usually live in one array in pairs: edge 2k and its reverse 2k + 1. The partner of edge e is then e ^ 1,
and pushing b units is two array updates. Each node keeps an adjacency list of edge indices.
Queue, stack and levels
- Edmonds–Karp searches with a FIFO queue (breadth-first), plus a parent array that records how each node was reached, so the path can be rebuilt backwards from t.
- Ford–Fulkerson here uses a stack (depth-first). The stack itself is the current path.
- Dinic keeps a level array from its breadth-first search and a "current arc" pointer per node. A pointer only moves forward, so an arc that leads to a dead end is never retried in the same phase. That's the trick behind its running time.
The algorithms
All three follow the augmenting path idea of Ford and Fulkerson: while there is a path from s to t with spare capacity in the residual graph, push the bottleneck amount along it. When no path is left, the flow is maximum. They differ in which path they pick.
| Algorithm | Which path | Time |
|---|---|---|
| Ford–Fulkerson | Any path; here the first one depth-first search finds | O(E · f*) for integer capacities |
| Edmonds–Karp | A shortest path (fewest edges), by breadth-first search | O(V · E²) |
| Dinic | All shortest paths at once, phase by phase | O(V² · E) |
| Push–relabel | No paths: nodes push excess downhill | O(V³) or better |
Plain Ford–Fulkerson depends on the size of the answer f*. On the classic four-node example with capacities of a million, an unlucky choice of paths makes two million pushes of one unit each. With irrational capacities it may never stop at all. Edmonds and Karp's fix is simply to use breadth-first search: shortest paths only get longer as the algorithm runs, which caps the number of rounds no matter how big the capacities are.
Push–relabel: a different idea
Augmenting-path methods keep a valid flow at all times and grow it path by path. Push–relabel, by Andrew Goldberg and Robert Tarjan, does the opposite. It starts by flooding every pipe out of s, which overloads the nodes behind them, and then repairs the overload locally. For a while it holds a preflow: nodes may receive more than they send, and that surplus is their excess.
Each node also has a height. Flow may only run downhill, from a node to a neighbor exactly one level lower, through an arc with spare room. A node with excess and no such arc gets relabeled: lifted to one above its lowest reachable neighbor. The source starts at a height equal to the number of nodes, so excess that can't reach t eventually climbs high enough to drain back to s. When no node holds excess, the preflow is a maximum flow.
Every operation looks at one node and its neighbors, which is why push–relabel parallelizes well and is the workhorse of fast solvers. Pick it in the lab and switch to "3D heights" to watch nodes rise and flow pour down the slopes.
Beyond this lab
- Minimum-cost flow. Edges also have a price per unit; send a required amount as cheaply as possible. It covers transportation and assignment problems.
- Multi-commodity flow. Several source and sink pairs share the same capacities. With integer flows required, it becomes NP-hard.
- Faster algorithms. Push–relabel (Goldberg and Tarjan) is the workhorse in practice. In 2022 Chen, Kyng, Liu, Peng, Probst Gutenberg and Sachdeva announced an algorithm running in almost-linear time, m1+o(1).
A little history
The problem came out of the Cold War. In 1955, T. E. Harris and F. S. Ross of the RAND Corporation studied the capacity of the Soviet and Eastern European rail network, and in particular the cheapest way to cut it. Lester Ford and Delbert Fulkerson proved the max-flow min-cut theorem in 1956 (Peter Elias, Amiel Feinstein and Claude Shannon found it independently the same year) and gave the augmenting path method. Yefim Dinitz published his blocking-flow algorithm in 1970, Jack Edmonds and Richard Karp their breadth-first rule in 1972, and Andrew Goldberg and Robert Tarjan push–relabel in 1988.