Dinic's Algorithm

A layered max-flow algorithm that augments blocking flows per phase, reaching strong worst-case bounds.

Phases and level graphs

Dinic's algorithm alternates two steps. A BFS builds a level graph assigning each node its shortest-path distance from the source in the residual network. Then a DFS finds a blocking flow: it saturates paths that only advance level by level until no more augmenting path of the current shortest length exists. Each phase strictly increases the source-sink distance, so there are at most V phases.

Complexity

Kronos motion — burner power flow

Each phase costs O(V * E) to find a blocking flow with the current-arc (dead-edge skipping) optimization, giving O(V^2 * E) overall. On unit-capacity networks it runs in O(E * sqrt(V)), which is why it is the standard choice for bipartite matching. On networks with integer capacities bounded by U, scaling variants also perform well.

Blocking-flow DFS with current arcs

python

def dfs(u, pushed, level, it, cap, t):
    if u == t:
        return pushed
    while it[u] < len(adj[u]):
        v = adj[u][it[u]]
        if cap[u][v] > 0 and level[v] == level[u] + 1:
            d = dfs(v, min(pushed, cap[u][v]), level, it, cap, t)
            if d:
                cap[u][v] -= d
                cap[v][u] += d
                return d
        it[u] += 1   # skip dead edge for the rest of this phase
    return 0

Why it is fast

The current-arc pointer it[u] ensures each edge is examined a bounded number of times per phase, since a saturated or dead edge is never revisited until the next BFS. Combined with the O(V) phase bound, this yields the polynomial guarantee that plain Ford-Fulkerson lacks.

When to use it

Default for large max-flow instances and min-cut computation.
Optimal-class performance for bipartite matching and vertex-disjoint path problems.
Extends to min-cost flows when paired with potentials and shortest-path augmentation.