Ford–Fulkerson / Augmenting Paths
Augmenting paths in the residual network give the maximum flow.
The idea
The Ford–Fulkerson method computes a maximum flow in a network. A flow network is a directed graph with a capacity $u(e) \ge 0$ on each edge, a source $s$, and a sink $t$. A flow $f$ assigns each edge an amount $0 \le f(e) \le u(e)$ so that every vertex other than $s$ and $t$ sends out exactly what it takes in; its value is the net amount leaving $s$.
Choosing paths greedily can fail, because an early path may occupy capacity that a better routing needs. The remedy is the residual network, which records for each edge how much more can be sent forward, $u(e) - f(e)$, and how much can be taken back — the $f(e)$ already placed, drawn as an edge pointing the opposite way. Rerouting mis-placed flow is then ordinary path-sending, along a backward residual edge.
Algorithm.
Algorithm: Ford–Fulkerson Input: a flow network — a directed graph with capacities u(e), a source s, a sink t Output: a maximum flow f 1. f(e) = 0 on every edge // f stays a valid flow throughout 2. form the residual network of f // each edge offers u(e) − f(e) forward and f(e) backward 3. look for an s–t path in the residual network, an augmenting path if none is left, return f 4. bottleneck = the smallest residual capacity among the path's edges 5. augment along the path: raise f by the bottleneck on each forward edge, lower it by the bottleneck on each backward edge 6. go to step 2
With integer capacities each augmentation raises the value by at least $1$, so the method terminates. When it does, the vertices still reachable from $s$ form one side of a cut whose capacity equals the flow's value, so no flow can do better: the flow is maximum, and its value equals the capacity of a minimum cut.
The figure below shows one run on a four-vertex network: a first path $s \to a \to b \to t$ fills two edges to capacity, the residual network then offers the backward edge $b \to a$, and a second augmenting path through it completes a maximum flow of value $12$.
Ways to work on it
- Walkthrough. Residual capacities, bottlenecks, and the stopping rule.
- Practice. Find the bottleneck and augment a path.
- Hardest. Reroute with a backward residual edge, then finish the maximum flow.
Not sure where to start? Take the ten-question placement test.