Residual network ($G_f$)

For a feasible flow $f$, each original directed edge $u\to v$ supplies a forward residual network edge of capacity $c_{uv}-f_{uv}$ and a backward one $v\to u$ of capacity $f_{uv}$; zero-capacity residual edges may be omitted. The forward edge permits an increase, while the backward edge permits cancellation of existing flow. In particular, backward residual capacity is the amount already sent, rather than unused original capacity. If both original orientations exist, keep their residual contributions separate, or add capacities for contributions with the same direction. An augmenting path uses these permitted changes while preserving flow conservation and the capacity constraints.

To see why cancellation matters, give all five directed edges $s\to a$, $s\to b$, $a\to b$, $a\to t$, $b\to t$ unit flow network edge capacities. Starting from zero flow, an augmenting path $s\to a\to b\to t$ carrying $1$ yieldsThe remaining unused original edges are $s\to b$ and $a\to t$, which do not form a source-to-sink graph path. However, the backward residual edge $b\to a$ has capacity $f_{ab}=1$. Consequently the residual network contains the augmenting path $s\to b\to a\to t$, with residual capacities $1,1,1$.

Augment by $1$: increase $f_{sb}$ and $f_{at}$ from $0$ to $1$, and decrease $f_{ab}$ from $1$ to $0$. The result isNow flow conservation is $1=0+1$ at $a$ and $1+0=1$ at $b$. The final flow sends one unit along each of $s\to a\to t$ and $s\to b\to t$. The cut of a flow network $S=\{s\}$ has cut capacity $1+1=2$, proving this is a maximum flow. Traversing $b\to a$ in the residual network revised the earlier routing decision; it did not send actual traffic along a nonexistent original edge.

For an undirected capacitated network, write the net edge flow as $y_{ij}=-y_{ji}$, and the directed residual capacity as $c_{ij}-y_{ij}$. On every source–sink cut, residual capacity is the original cut capacity minus the current net flow value $f$. Taking the minimum over cuts and applying the max-flow min-cut theorem to each network gives the displayed remaining-flow identity.

An augmenting path is a source-to-sink graph path $P$ of positive capacities in the residual network. Its bottleneck is $\Delta ={\min }_{e\in P}{c}_f(e)>0$. Add $\Delta$ to original flow on forward residual edges and subtract $\Delta$ on backward residual edges. Each internal vertex still satisfies flow conservation, and the bottleneck guarantees every capacity constraint. The resulting feasible flow has strength of a flow $|f|+\Delta$. In the unit-capacity residual network example, $\Delta =1$, and the subtraction on $a\to b$ is precisely what allows the value to rise from $1$ to $2$.

An augmenting path maximizing the possible increase in flow, namely its smallest residual network edge capacity. If the remaining maximum flow is $F>0$ and the original undirected network has $m$ edges, a path has bottleneck at least $F/m$. Otherwise the vertices reachable through arcs of capacity at least $F/m$ define a cut of capacity strictly less than $F$, contradicting the max-flow min-cut theorem. Only one directed arc per original crossing edge contributes to that cut.

Starting from zero flow, a widest augmenting path increases the current flow by at least $F_k/m$, where $F_k$ is its remaining optimality gap. Therefore $F_{k+1}\le (1-1/m)F_k$. Integer capacities keep this gap integer, so a gap below one is zero. The method takes $O(m\log f^{\ast })$ augmentations for $f^{\ast }\ge 2$, or uniformly $O(m\log (1+f^{\ast }))$; zero maximum flow requires no augmentation.

The Ford-Fulkerson algorithm repeatedly augments a feasible flow along an augmenting path. When no such path remains, the source-reachable vertices in the residual network define a cut of capacity equal to the flow value, proving optimality by the max-flow min-cut theorem.

Starting from the zero flow with integer capacities, every residual capacity and every augmenting bottleneck is an integer. Each augmentation therefore preserves integer edge flows and raises the flow value by at least one. Since the value is bounded by the total capacity leaving the source, the algorithm terminates after finitely many augmentations with an integral maximum flow.