Edmonds-Karp Algorithm
What you'll learn: How using BFS to find augmenting paths in the Ford-Fulkerson method creates a faster, more predictable algorithm with guaranteed O(VE²) time complexity.
The Core Problem with Ford-Fulkerson
The Ford-Fulkerson method you just learned is powerful but has a weakness: it doesn't specify how to find augmenting paths. If you choose paths poorly (say, using DFS), the algorithm might take an unpredictable amount of time—or even fail to terminate with irrational capacities.
The Edmonds-Karp Solution
Edmonds-Karp is simply Ford-Fulkerson with a specific rule: always find the shortest augmenting path using BFS (Breadth-First Search).
Think of it like this: if you're filling a water network, instead of randomly exploring pipes, you always choose the route with the fewest pipe segments from source to sink. This "shortest path first" strategy guarantees you won't waste iterations on inefficient routes.
Why BFS Changes Everything
By measuring path length in number of edges (not capacity), BFS ensures:
- Each augmenting path is shortest in the residual network
- The algorithm terminates in at most O(VE) iterations
- Each BFS takes O(E) time with adjacency lists
Total complexity: O(VE²) — predictable and polynomial, unlike vanilla Ford-Fulkerson.
The Guarantee
The key insight: using shortest paths prevents the algorithm from "undoing" progress. The distance from source to sink in the residual graph never decreases, and edges become saturated in a controlled way. After at most VE flow augmentations, you've found the maximum flow.
Key Takeaway: Edmonds-Karp is Ford-Fulkerson with BFS for finding shortest augmenting paths, guaranteeing O(VE²) time complexity and making maximum flow practical for real-world graphs.