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

Edmonds-Karp Algorithm

Learn Ford-Fulkerson with BFS for shortest augmenting paths, guaranteeing O(VE²) time complexity.

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:

  1. Each augmenting path is shortest in the residual network
  2. The algorithm terminates in at most O(VE) iterations
  3. 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.