The Ford-Fulkerson Algorithm
You'll learn how the Ford-Fulkerson method systematically finds the maximum flow in a network by repeatedly discovering and augmenting paths.
The Core Idea
The Ford-Fulkerson algorithm is a practical technique for computing the maximum flow in a flow network. It works by starting with zero flow and repeatedly finding augmenting paths—routes from source to sink with available capacity—then pushing as much flow as possible along each path until no more augmenting paths exist.
The algorithm uses a residual network, which shows remaining capacities. For each edge with flow f and capacity c, the residual network includes:
- A forward edge with remaining capacity (c - f)
- A backward edge with capacity f (allowing flow reversal)
How It Works
- Initialize all flows to zero
- Search for an augmenting path in the residual network from source to sink
- Find the bottleneck: the minimum residual capacity along the path
- Augment the flow by adding the bottleneck amount to each edge on the path
- Update the residual network
- Repeat steps 2-5 until no augmenting path exists
When the algorithm terminates, the current flow is maximum (by the Max-Flow Min-Cut Theorem you just learned).
Analogy
Think of water flowing through pipes. Ford-Fulkerson repeatedly finds any open route and pushes as much water as possible through it, then looks for another route. The backward edges let you "undo" earlier poor routing decisions by redirecting flow.
Key Takeaway: The Ford-Fulkerson algorithm computes maximum flow by iteratively finding augmenting paths in the residual network and increasing flow along them until no more paths exist.