AlgoScope

Dinic

Build a level graph with BFS, then push blocking flows with DFS. O(V^2 E).

Network flow, algorithm, expert
Phase 1, sink at level 3.0/160/130/120/40/140/90/200/70/4001121324253
Phase 1, sink at level 3.0/160/130/120/40/140/90/200/70/4001121324253

Maximum Flow: Dinic: level graphs and blocking flows

Decision, step 2 of 13

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.

How maximum flow works

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.

Taught by the same lesson

Maximum Flow covers these too, in the same run.