Edmonds-Karp
Ford-Fulkerson with BFS, so each path is shortest; O(V E^2) regardless of capacities.
Decision · step 2 of 9Maximum 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.
What you will see
BFS finds the fewest-edge path each round.
Cost
| Best | O(E) |
|---|---|
| Average | O(V * E^2) |
| Worst | O(V * E^2) |
| Space | O(V + E) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input.
Screen readers: Edges announce capacity, flow and residual; each step announces the augmenting path and bottleneck.
Reduced motion: Flow labels update with a crossfade; the augmenting path is emphasized statically.
Before this
A variant of
Taught by the same lesson
Maximum Flow covers these too, in the same run.