AlgoScope

Minimum Cut

The vertices still reachable in the final residual graph are S. The saturated edges leaving S sum to the max flow.

Network flow, analysis, advanced
Augmenting path 0 to 1 to 3 to 5, bottleneck 5.0/100/80/20/50/100/30/70/10012345
Augmenting path 0 to 1 to 3 to 5, bottleneck 5.0/100/80/20/50/100/30/70/10012345

Maximum Flow: Min cut of the same network

Decision, step 2 of 11

BFS finds the shortest augmenting path 0 > 1 > 3 > 5, residual capacities 10, 5, 7. The bottleneck is 5.

How maximum flow works

Cost

Space
O(V + E)

Taught by the same lesson

Maximum Flow covers these too, in the same run.