Dinic's Algorithm

Builds a BFS 'level graph' from S each phase, then pushes a full blocking flow (multiple paths at once, all following increasing levels) via DFS before rebuilding the level graph. Far fewer phases than Edmonds-Karp's one-path-at-a-time approach.

Category

Graphs

Time complexity

O(V²E)

Space complexity

O(V + E)

Pseudocode

while BFS from S reaches T (level graph exists):
  repeatedly DFS a level-respecting path, push its bottleneck
  (this is one "blocking flow" phase)
rebuild level graph; stop when T unreachable

Reference implementation

while level := bfs_levels(residual_graph, S):
    if T not in level: break
    while path := dfs_level_respecting(S, T, level):
        b = min(residual capacities on path)
        for edge in path: update_flow(edge, b)
        flow += b

Open the interactive Dinic's Algorithm visualisation →