Course contentsShow
← Computer Science
Lesson 1038 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Ford-Fulkerson Method

Understand the iterative framework: find augmenting paths, update flow, and repeat until no paths exist.

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.