Ford-Fulkerson Method
What You'll Learn
You'll learn how the Ford-Fulkerson method finds maximum flow by iteratively discovering augmenting paths and updating flow until no more paths exist.
The Iterative Framework
The Ford-Fulkerson method is not a single algorithm but a framework for solving the maximum flow problem. Think of it like a recipe: it tells you what to do, but not exactly how to do each step.
Here's the framework in three steps:
1. Find an Augmenting Path
Start with zero flow. Search the residual network for any path from source to sink where every edge has positive residual capacity (an augmenting path). You can use any search method—DFS, BFS, or even random exploration.
2. Update the Flow
Once you find an augmenting path, determine its residual capacity (the bottleneck—the smallest capacity along the path). Push that much flow along the path by:
- Increasing flow on forward edges
- Decreasing flow on backward edges (updating the residual network)
3. Repeat Until No Paths Exist
Go back to step 1. Keep finding augmenting paths and updating flow. When you can no longer find any augmenting path from source to sink, you've found the maximum flow.
Why It Works
The method relies on the augmenting path theorem: a flow is maximum if and only if there are no augmenting paths in the residual network. Each iteration increases the total flow, and when no path exists, you're done.
Practical Note
The efficiency of Ford-Fulkerson depends on how you find augmenting paths. Poor path selection can lead to slow convergence or even non-termination with irrational capacities. Specific implementations (like Edmonds-Karp) address this by choosing paths systematically.
Key Takeaway: The Ford-Fulkerson method iteratively finds augmenting paths, augments flow along them, and terminates when no augmenting paths remain—guaranteeing maximum flow.