Scriba — dinic

Dinic's Algorithm — Max Flow

Overview

Dinic's algorithm finds max flow in

O(V^2 E)

by repeatedly:

Build a level graph via BFS (assign distance labels from

s

)

Find blocking flows via DFS (saturate all shortest paths at once)

Each BFS phase increases the shortest

s

t

distance by at least 1, so at most

V-1

phases.

\text{Time: } O(V^2 E) \quad \text{vs Edmonds-Karp } O(VE^2)

Walkthrough

Step 1 / 19

Flow network with 6 nodes, 8 edges. Each edge shows flow/capacity. Dinic's alternates BFS (level graph) and DFS (blocking flow).

Step 2 / 19

Phase 1 — BFS: Build level graph. $level[S]=0$ , expand layer by layer.

Step 3 / 19

From $S$ : reach $A$ and $B$ . $level[A]=1$ , $level[B]=1$ .

Step 4 / 19

From $A$ , $B$ : reach $C$ and $D$ . $level[C]=2$ , $level[D]=2$ . Edge $A \to B$ skipped (same level).

Step 5 / 19

From $C$ , $D$ : reach $T$ . $level[T]=3$ . Level graph complete. Only edges going from level $k$ to $k+1$ are kept.

Step 6 / 19

Phase 1 — DFS 1: Find path $S \to A \to C \to T$ . Bottleneck $= \min(10, 8, 10) = 8$ . Push 8.

Step 7 / 19

Update: $S \to A$ : 8/10, $A \to C$ : 8/8 (saturated!), $C \to T$ : 8/10. Total $= 8$ .

Step 8 / 19

Phase 1 — DFS 2: $A \to C$ saturated. DFS backtracks, tries $S \to B \to C \to T$ . Bottleneck $= \min(10, 6, 2) = 2$ .

Step 9 / 19

Push 2. $C \to T$ : 10/10 (saturated!). Total $= 10$ .

Step 10 / 19

Phase 1 — DFS 3: $C \to T$ saturated. DFS tries $S \to B \to D \to T$ . Bottleneck $= \min(8, 5, 10) = 5$ .

Step 11 / 19

Push 5. $B \to D$ : 5/5 (saturated!). Total $= 15$ .

Step 12 / 19

Phase 1 — DFS done: No more paths to $T$ in level graph. All edges from $B$ to level-2 are saturated ( $B \to C$ : 2/6? No, residual $= 4$ ). Actually $C \to T$ saturated blocks $C$ . $B \to D$ saturated blocks $D$ . Blocking flow complete.

Step 13 / 19

Phase 2 — BFS: Rebuild level graph on residual. Reverse edges now exist: $C \to A$ (cap 8), $T \to C$ (cap 10), etc.

Step 14 / 19

Level graph same structure ( $T$ still at level 3). But available edges differ due to residual capacities. Key: $S \to A$ has 2, $A \to B$ has 2, $B \to C$ has 4, $C \to T$ saturated — must use reverse $C \to A$ (8) and reroute.

Step 15 / 19

Phase 2 — DFS: Path $S \to A \to B \to D \to T$ (via residual). $S \to A$ : 2, $A \to B$ : 2, $B \to D$ saturated\ldots no. Try $S \to B \to C \to D \to T$ . $S \to B$ : 3, $B \to C$ : 4, $C \to D$ : 3, $D \to T$ : 5. Bottleneck $= 3$ .

Step 16 / 19

Push 3. $S \to B$ : 10/10 (saturated!). $B \to C$ : 5/6. $C \to D$ : 3/3 (saturated!). $D \to T$ : 8/10. Total $= 18$ .

Step 17 / 19

Phase 2 — DFS 2: $S \to B$ saturated. Try $S \to A$ (residual 2). $A \to B$ : 2, $B \to C$ : 1, but $C \to T$ saturated and $C \to D$ saturated. $A \to B \to D \to T$ ? $B \to D$ saturated. Dead end. Blocking flow done.

Step 18 / 19

Phase 3 — BFS: $S$ can reach $A$ (residual 2). From $A$ : $A \to B$ (2). From $B$ : $B \to C$ (1). From $C$ : $C \to T$ saturated. No path to $T$ in residual $\Rightarrow$ BFS fails. Algorithm terminates.

Step 19 / 19

Max flow $= 18$ . Min-cut: reachable from $S$ in residual $= \{S,A,B\}$ vs $\{C,D,T\}$ . Cut edges (red): $A \to C$ (8) + $B \to C$ (6) + $B \to D$ (5). Dinic's found this in 2 BFS phases.

Why Dinic's is Faster

Edmonds-Karp: one augmenting path per BFS.

O(VE)

paths total

\Rightarrow O(VE^2)

Dinic's: one BFS builds level graph, then DFS finds all shortest augmenting paths (blocking flow) at once. Each phase increases shortest path length

\Rightarrow

at most

V-1

phases, each

O(VE)

\Rightarrow O(V^2 E)

Key optimization: the iter[] array (current-arc optimization) ensures each edge is examined at most once per DFS phase.

Implementation

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]

    def add_edge(self, u, v, cap):
        self.graph[u].append([v, cap, len(self.graph[v])])
        self.graph[v].append([u, 0, len(self.graph[u]) - 1])

    def bfs(self, s, t):
        """Build level graph. Return True if t reachable."""
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v, cap, _ in self.graph[u]:
                if cap > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1
                    q.append(v)
        return self.level[t] >= 0

    def dfs(self, u, t, pushed):
        """Find blocking flow via DFS with current-arc optimization."""
        if u == t:
            return pushed
        while self.iter[u] < len(self.graph[u]):
            e = self.graph[u][self.iter[u]]
            v, cap, rev = e
            if cap > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(pushed, cap))
                if d > 0:
                    e[1] -= d
                    self.graph[v][rev][1] += d
                    return d
            self.iter[u] += 1
        return 0

    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):          # Phase: build level graph
            self.iter = [0] * self.n    # Reset current-arc pointers
            while True:                 # Find all blocking flows
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f
        return flow