AlgoScope

Ford-Fulkerson

Any augmenting path will do. Push its bottleneck, and undoing flow along a backward residual edge is allowed.

Network flow, algorithm, advanced
Augmenting path 0 to 1 to 2 to 3, bottleneck 1.0/10/10/10/10/10123
Augmenting path 0 to 1 to 2 to 3, bottleneck 1.0/10/10/10/10/10123

Maximum Flow: Ford-Fulkerson with a cancelled edge

Decision, step 2 of 7

DFS finds an augmenting path 0 > 1 > 2 > 3, residual capacities 1, 1, 1. The bottleneck is 1.

How maximum flow works

Cost

Best
O(E)
Average
O(E * max flow)
Worst
O(E * max flow)
Space
O(V + E)

May not terminate with irrational capacities.

Leads to

Topics that need this one first.

Taught by the same lesson

Maximum Flow covers these too, in the same run.