Augmenting Path¶

Definition¶

An augmenting path is a source-to-sink path in the residual network with strictly positive residual capacity in every traversed direction. Its residual capacity, or bottleneck, is

\delta=\min_{e\text{ on the path}}r_e.

An additional $\delta$ units of net source-to-sink flow can be assigned along it.

Interpretation¶

An augmenting path is a route from source to sink along which more flow can still be sent. The smallest remaining capacity on it, the bottleneck $\delta$ , limits the whole path: sending more than $\delta$ would overload that edge.

A network from A to F with flow and capacity on each edge and current flow value 5; the path A, C, E, F with residual capacities 3, 4 and 3 is highlighted, and augmenting it by 3 raises the flow to 8.

Labels are flow/capacity, and the current flow value is $3+2=5$ out of $A$ . The red path $A-C-E-F$ has residual capacities $5-2=3$ $3$ , $4-0=4$ and $3-0=3$ $3$ , so $\delta=3$ $3$ ; after sending $3$ more units, $A-C$ and $E-F$ are both full and the value is $8$ . The bottleneck uses residual capacities, not capacities: $A-C$ has capacity $5$ , but only $3$ of it is still free.

A path may also use the reverse direction of an original edge, which the residual network offers with residual capacity equal to the current flow on that edge. Traversing it takes back flow sent earlier and reroutes it. Such a backward segment reduces an original flow while still increasing the total source-to-sink value, and flow conservation at every intermediate vertex still holds.

Augmenting paths drive the augmenting path algorithm, which stops when none is left. In the figure, after the augmentation both edges into $F$ are full and no residual capacity leads into $F$ , so no augmenting path remains and $8$ is the maximum flow.

Key Results¶

All residual directions on the path must be feasible.
Augmenting by the bottleneck saturates at least one residual direction.
A path may use both forward and reverse directions relative to original edges.

Examples¶

The illustrated edge labels are flow/capacity. The red path $A-C-E-F$ has residual capacities $3,4,3$ , so $\delta=\min(3,4,3)=3$ increases total flow from 5 to 8. A feasible flow is maximum exactly when no source-to-sink augmenting path remains.

The first S-A-D-T augmentation in the video has bottleneck 5.
A later S-B-E-D-A-C-T path cancels part of the earlier A-D flow and adds two units overall.

Prerequisites¶

Augmenting Path Algorithm

Sources¶

OR Modelling · Week 4

Aliases: flow-augmenting path Symbols: delta

Last updated: 20 October 2026 03:02