Maximum Flow: Ford-Fulkerson Method

Imagine a network of water pipes. Water enters at one special node called the source (we'll call it node 0) and must leave at another special node called the sink (node 5). Every pipe has a capacity — the most water it can carry per second.

A flow assigns a number to each pipe saying how much water actually goes through it. A flow has to obey two rules:

1. Capacity rule: the flow on a pipe can never exceed its capacity.
2. Conservation rule: for every node except the source and sink, the water coming in equals the water going out. Nothing is created or lost in the middle.

The value of a flow is the total amount leaving the source (which also equals the total arriving at the sink). The maximum flow problem asks: what is the largest value we can achieve?

In our example network the answer turns out to be 23.

The clever idea behind Ford-Fulkerson is the residual graph. It tracks how much more flow each edge can still take.

For a forward edge u → v with capacity c and current flow f, the residual capacity is c − f — the room that's left.

Here's the subtle part: pushing f units along u → v also creates a backward (residual) edge v → u with residual capacity f. This backward edge lets the algorithm cancel or reroute flow it sent earlier if that turns out to be a mistake.

Tiny example: suppose edge 1 → 3 has capacity 12 and we've pushed 12 units. Its forward residual is 12 − 12 = 0 (full), but now there is a backward edge 3 → 1 with residual 12. Later the algorithm can send flow 3 → 1 to undo some of that choice.

An augmenting path is any path from the source to the sink that uses only edges with residual capacity > 0. The amount we can push along it is the bottleneck — the smallest residual capacity on the path.

The method is wonderfully simple — just repeat one idea until you can't anymore:

1. Build the residual graph for the current flow.
2. Find any augmenting path from source to sink (here we use DFS).
3. Compute its bottleneck = the minimum residual capacity along the path.
4. Push that many units: subtract the bottleneck from each forward residual edge and add it to each backward residual edge.
5. Add the bottleneck to the total flow.
6. Repeat. When no augmenting path exists, the current flow is maximum.

Each augmenting path strictly increases the total flow, so with integer capacities the process always ends.

Watch Ford-Fulkerson run on the example network. The source is node 0 and the sink is node 5. Each edge is labelled flow / capacity. On each round the algorithm highlights an augmenting path (amber, dashed), shows its bottleneck, then pushes that much flow and updates the totals. It stops when no augmenting path remains — the final total is the maximum flow, 23.

Why are we sure the algorithm stops at the true maximum and isn't just stuck?

A cut splits the nodes into two groups: one containing the source, the other containing the sink. The capacity of the cut is the total capacity of all edges crossing from the source's side to the sink's side. Every unit of flow must cross any such cut, so no flow can ever exceed the smallest cut's capacity.

The max-flow min-cut theorem says these two quantities are actually equal: the maximum flow value equals the minimum cut capacity. When Ford-Fulkerson can no longer find an augmenting path, the nodes still reachable from the source in the residual graph form exactly such a minimum cut — proving the flow we found is optimal.

The body below repeatedly finds an augmenting path and pushes its bottleneck. The residual updates (-= b forward, += b backward) are what let the algorithm reconsider earlier decisions.

Each augmenting path adds at least 1 unit of flow (with integer capacities), and finding a path with DFS costs O(V + E). So the running time is O(E · |f*|), where |f*| is the maximum-flow value. This is fine for small capacities but can be slow when capacities are huge, because the number of paths depends on the flow value rather than the graph size. Choosing the shortest augmenting path with BFS instead of DFS gives the Edmonds-Karp algorithm, which runs in O(V · E²) regardless of capacities.

Step through the algorithm at your own pace. Use the controls to move forward and backward, play the animation, or reset. Watch how the residual backward edges let flow get rerouted to reach the maximum of 23.