Augmenting Path Algorithm¶

Definition¶

The augmenting path algorithm starts with a feasible flow, initially zero in the course examples. Find a source-to-sink augmenting path, augment by its bottleneck $\delta$ , decrease each traversed residual capacity by $\delta$ , increase the opposite residual capacity by $\delta$ , and repeat. If no augmenting path remains, the current flow is maximum.

Interpretation¶

The augmenting path algorithm builds a maximum flow step by step: as long as some route from source to sink still has spare capacity, it sends as much as that route allows. The residual network keeps track of the spare capacity and allows both new routing and correction of earlier routing.

A vertical sequence of steps: three augmenting paths with bottlenecks 3, 3 and 2 raise the flow value from 0 to 8, after which no augmenting path remains.

The figure runs the algorithm from zero flow on the network of the augmenting path figure. Three paths are found, with bottlenecks $3$ , $3$ and $2$ , raising the flow value to $3$ , $6$ and $8$ . At the end both edges into $F$ are full: $D-F$ carries $5$ and $E-F$ carries $3$ . Every unit reaching $F$ uses one of them, so no flow can exceed $8$ : the stopping condition has certified a maximum.

The reverse residual directions are not a technicality. Take edges $S\to A$ $A$ , $S\to B$ $B$ , $A\to B$ $B$ , $A\to T$ and $B\to T$ $T$ , all of capacity $1$ . After a first path $S-A-B-T$ $T$ , no forward route with spare capacity is left, although the maximum flow is $2$ . The reverse residual $B\to A$ of the used edge $A\to B$ gives the path $S-B-A-T$ $T$ , which cancels that unit on $A\to B$ and reaches the maximum.

The final flow value does not depend on which augmenting paths are chosen, although the flows on individual edges can. A common slip is to read the final residual capacities as flows: the flow on an original edge equals its reverse residual.

Key Results¶

Maintain flow conservation after every augmentation.
The integer capacities in the exercises allow integer augmentations and finite termination.
Recover original flows from the final residual values, taking edge directions into account.

Examples¶

On an original forward edge the augmentation adds $\delta$ to its flow; on a backward residual edge it subtracts $\delta$ . With integer capacities and an integral starting flow, each augmentation increases the value by at least 1, so only finitely many are possible.

The main example augments by $5,2,1,4,1,2$ , totalling 15.
The last residual network cannot reach the sink T from the source S through positive residual directions.

Prerequisites¶

Sources¶

OR Modelling · Week 4

Aliases: Ford-Fulkerson method, Ford-Fulkerson algorithm, augmenting path method Symbols: delta

Last updated: 20 October 2026 03:02