Edmonds-Karp
Ford-Fulkerson with BFS, so each path is shortest. O(V E^2) regardless of capacities.
Maximum Flow: Edmonds-Karp, shortest paths first
BFS finds the shortest augmenting path 0 > 1 > 3 > 5, residual capacities 10, 5, 7. The bottleneck is 5.
Cost
- Best
- O(E)
- Average
- O(V * E^2)
- Worst
- O(V * E^2)
- Space
- O(V + E)
Before this
A variant of
Leads to
Topics that need this one first.
Taught by the same lesson
Maximum Flow covers these too, in the same run.