Ford-Fulkerson
Any augmenting path will do; push its bottleneck, and undoing flow along a backward residual edge is allowed.
Decision · step 2 of 7Maximum Flow: Ford-Fulkerson with a cancelled edge
DFS finds an augmenting path 0 > 1 > 2 > 3, residual capacities 1, 1, 1. The bottleneck is 1.
What you will see
A path lights up, its bottleneck is found, flow labels increase and residual edges appear.
Cost
| Best | O(E) |
|---|---|
| Average | O(E * max flow) |
| Worst | O(E * max flow) |
| Space | O(V + E) |
May not terminate with irrational capacities.
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
Related
Taught by the same lesson
Maximum Flow covers these too, in the same run.