AlgoScope

Edmonds-Karp

Ford-Fulkerson with BFS, so each path is shortest. O(V E^2) regardless of capacities.

Network flow, algorithm, 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: Edmonds-Karp, shortest paths first

Decision, step 2 of 9

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

Cost

Best
O(E)
Average
O(V * E^2)
Worst
O(V * E^2)
Space
O(V + E)

A variant of

Leads to

Topics that need this one first.

Taught by the same lesson

Maximum Flow covers these too, in the same run.