Ford-Fulkerson
Any augmenting path will do. Push its bottleneck, and undoing flow along a backward residual edge is allowed.
Maximum 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.
Cost
- Best
- O(E)
- Average
- O(E * max flow)
- Worst
- O(E * max flow)
- Space
- O(V + E)
May not terminate with irrational capacities.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Maximum Flow covers these too, in the same run.