Dinic
Build a level graph with BFS, then push blocking flows with DFS; O(V^2 E).
Phase 1: BFS levels 0 at 0, 1 at 1, 2 at 1, 3 at 2, 4 at 2, 5 at 3; 5 is at level 3, so every shortest augmenting path has 3 edges. The highlighted edges are the level graph: residual edges from a level to the next. Everything else is ignored until the phase ends.
What you will see
Levels drawn as columns; several augmenting paths per phase.
Cost
| Best | O(E) |
|---|---|
| Average | O(V^2 * E) |
| Worst | O(V^2 * E) |
| Space | O(V + E) |
O(E sqrt(V)) on unit-capacity networks.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input.
Screen readers: Edges announce capacity, flow and residual; each step announces the augmenting path and bottleneck.
Reduced motion: Flow labels update with a crossfade; the augmenting path is emphasized statically.
Before this
Taught by the same lesson
Maximum Flow covers these too, in the same run.