📜 WAYPOINT LESSON
Augmenting Paths and the Min Cut
⭐⭐⭐ advanced⏳ 35 min read📍 Lesson 154 of 281
BFS finds the shortest augmenting path; when none remains, the set reachable from s IS the min cut — max-flow = min-cut falls out.
From augmentations to the cut
Edmonds–Karp: BFS the residual graph, push the bottleneck, repeat. When BFS finds no path, S = reachable-from-s: every original edge S→outside is saturated, every outside→S edge is empty — cut capacity = flow value.
Dinic (BFS level graph + DFS blocking flow) is the default for the course's load tests; Edmonds–Karp is for teaching and small m.