= Solution
The <Ford-Fulkerson algorithm> starts with zero <flow>. For each original edge $i\to j$, the <residual network> has a forward edge with residual capacity $c_{ij}-f_{ij}$ and a reverse edge with residual capacity $f_{ij}$. Distinguish these labelled residual edges if the original graph has antiparallel edges. While there is a source-to-sink <augmenting path> with positive residual capacities, increase the <flow> by the minimum residual capacity along it, adding on forward edges and subtracting on reverse edges. This preserves capacity bounds and <flow conservation> and increases the <strength of a flow> by that positive bottleneck.
A <cut of a flow network> is a partition $(S,V\setminus S)$ with $s\in S$, $t\notin S$, of capacity $c(S)=\sum_{i\in S,j\notin S}c_{ij}$. Summing <flow conservation> gives $|f|=f(S,V\setminus S)-f(V\setminus S,S)\leq c(S)$. The <max-flow min-cut theorem> states
$$
\boxed{\max_f|f|=\min_{S:s\in S,\,t\notin S}c(S)}.
$$
When no <augmenting path> remains, take $S$ to be the vertices reachable from $s$ in the <residual network>. Every original outgoing edge of this <cut of a flow network> is saturated and every incoming edge has zero <flow>; otherwise a positive residual edge would leave $S$. Thus $|f|=c(S)$, certifying optimality and the theorem. For general finite real capacities, one can also apply this argument to an existing maximum: it cannot admit an <augmenting path>.
With integer capacities, each augmentation increases the value by at least one, so the <Ford-Fulkerson algorithm> terminates. Rational capacities can be scaled to integers. Arbitrary path choices with irrational capacities need not terminate; the existence theorem does not justify claiming finite termination in that generality. The given network has integer capacities, so this caveat does not obstruct its computation.
Back to article page
