= Solution
A <maximum flow> problem specifies a finite directed <flow network>, a source $s$, a sink $t$, and nonnegative arc capacities. A feasible flow assigns $0\leq f_e\leq c_e$ to each arc, with incoming flow equal to outgoing flow at each vertex other than $s,t$. The objective is to maximize the net flow leaving $s$, equivalently entering $t$.
The <Ford-Fulkerson algorithm> starts with zero flow. Its <residual network> has a forward arc of capacity $c_e-f_e$ and a reverse arc of capacity $f_e$ for each original arc. If an $s$–$t$ path has positive residual capacities, augment by their minimum: increase flow along forward arcs and decrease it along reverse arcs. This preserves capacity bounds and conservation, and increases the flow value by that positive bottleneck. Repeat until there is no augmenting path.
For rational capacities, choose a positive integer $D$ clearing every denominator. Initially all flows and residual capacities are integer multiples of $1/D$, and augmentation preserves that property. Every augmentation therefore increases the flow value by at least $1/D$. The flow value is bounded above by the sum of capacities of arcs leaving $s$. Thus only finitely many augmentations can occur, independently of how the augmenting paths are chosen.
To see why termination supplies a maximum, let $S$ consist of vertices reachable from $s$ in the final residual network. The sink is not in $S$. Each original arc from $S$ to its complement is saturated; each original arc entering $S$ has zero flow, since otherwise its reverse residual arc would leave $S$. The resulting flow value equals the capacity of this cut. No feasible flow exceeds a cut capacity. Hence \b[the algorithm terminates at a maximum flow for rational capacities], proving the relevant <max-flow min-cut theorem> conclusion as well.
Back to article page
