= Augmenting path
{title2=$\Delta=\min_{e\in P}c_f(e)>0$}
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$.
Back to article page
