Dinic
Build a level graph with BFS, then push blocking flows with DFS. O(V^2 E).
Maximum Flow: Dinic: level graphs and blocking flows
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.
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.
Before this
Taught by the same lesson
Maximum Flow covers these too, in the same run.