The augmenting path idea
The Ford Fulkerson method computes maximum flow by repeatedly finding an augmenting path from source to sink that still has spare room, then pushing as much flow as that path allows. When no augmenting path remains, the flow is maximum.
The residual graph
The trick is the residual graph. For each edge with some capacity left, a forward residual edge records the remaining room. For each unit of flow already sent, a backward residual edge of equal size is added, letting later steps cancel and reroute earlier choices. Without these backward edges the method could get stuck on a greedy mistake.
One iteration
- Search the residual graph for any path from source to sink.
- Find the bottleneck, the smallest residual capacity along that path.
- Add the bottleneck amount of flow forward and subtract it on the backward edges.
Repeat until the search finds no path. The accumulated flow is then maximum, which also exposes the minimum cut: the nodes still reachable from the source form one side.
A caution
If you always pick the shortest augmenting path by edge count, the method becomes the Edmonds Karp algorithm and terminates in a predictable number of steps. Choosing paths carelessly with irrational capacities can fail to terminate.
Key idea
Ford Fulkerson grows the flow one augmenting path at a time, using backward residual edges to undo earlier choices until no spare path is left.