What you're seeing
Picture pipes from a source S to a sink T, each with a capacity. How much can flow at once? Ford–Fulkerson's idea: as long as there's a path from S to T with spare capacity on every edge — an augmenting path — push as much as its tightest edge allows, then look for another. The subtlety is the residual graph: pushing flow along an edge also opens a virtual reverse edge, letting later paths cancel earlier flow and reroute it — which is what lets the method always reach the true optimum. Edmonds–Karp simply always picks the shortest augmenting path (via BFS), which guarantees it finishes quickly. When no augmenting path is left, the flow is maximum.
The rule
flow = 0 everywhere
while BFS finds a path S → T with spare (residual) capacity:
b = min residual capacity along the path # the bottleneck
add b to the flow on each forward edge,
subtract b on each reverse (residual) edge
return total flow leaving S
The invariant
The headline result is the max-flow / min-cut theorem: the maximum flow value equals the capacity of the minimum cut — the cheapest set of edges whose removal severs S from T. One direction is easy: any flow is bounded by any cut, since everything reaching T must cross it, so max-flow ≤ min-cut. The algorithm proves the other direction constructively. When BFS can find no more augmenting paths, let A be the set of nodes still reachable from S in the residual graph (S ∈ A, T ∉ A). Every edge from A to its complement must be saturated (or it would leave residual capacity and T would be reachable), and every edge coming back into A carries zero flow — so the flow across this cut equals its full capacity, and equals the total flow. A flow that meets a cut's capacity is maximum and that cut is minimum. That's the cut the animation paints orange at the end.
The cost
Choosing the shortest augmenting path (BFS) is what tames Ford–Fulkerson: the BFS distance from S to T never decreases and each edge can become a bottleneck only O(V) times, giving O(VE²) — crucially, a bound that doesn't depend on the capacity values (naive Ford–Fulkerson with bad choices can take time proportional to the max flow, which can be huge). Dinic's algorithm (blocking flows on the BFS level graph) improves this to O(V²E), and to O(E√V) on unit-capacity graphs — the bound behind fast bipartite matching. Modern max-flow has been pushed all the way to almost-linear time (Chen et al., 2022).
In the wild
Max-flow is one of the most reductions-rich problems in computing. Bipartite matching (job assignment, scheduling, ad allocation) is a unit-capacity flow; image segmentation in vision is a min-cut; it models network/road throughput and reliability, airline crew scheduling, baseball-elimination and project-selection problems, and — via min-cut — community detection and "is this network robust?" questions. The duality with min-cut makes it a Swiss-army knife: phrase your problem as "separate these from those at least cost" and a flow solver answers it.
Try this
Step through the augmenting paths: each green path pushes its bottleneck, and watch edges turn purple as they saturate. When the search finally fails, the network splits — the blue reachable side and the rest — and the orange edges between them are the min cut. Add up their capacities (the readout's "min cut") and you'll find it exactly equals the flow value. Hit New capacities and the bottleneck moves, but the equality never breaks.
References
- Ford, L. R. & Fulkerson, D. R. "Maximal flow through a network." Canadian Journal of Mathematics 8:399–404, 1956.
- Edmonds, J. & Karp, R. M. "Theoretical improvements in algorithmic efficiency for network flow problems." Journal of the ACM 19(2):248–264, 1972.
- Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §24 (Maximum Flow). MIT Press, 2022.