Scriba — maxflow

Maximum Flow — Edmonds-Karp Algorithm

Problem

Given a directed graph

G = (V, E)

with source

s

and sink

t

, each edge

(u,v)

has capacity

c(u,v)

. Find the maximum flow from

s

t

respecting capacity constraints.

\text{maximize} \quad \sum_{v} f(s,v) \quad \text{subject to} \quad 0 \le f(u,v) \le c(u,v)

Edmonds-Karp = Ford-Fulkerson with BFS for shortest augmenting paths. Guarantees

O(VE^2)

Algorithm Walkthrough

Step 1 / 15

Flow network: each edge shows flow/capacity. All flows start at 0. Goal: maximize flow from $S$ to $T$ .

Step 2 / 15

Iteration 1: BFS from $S$ finds shortest path $S \to A \to C \to T$ .

Step 3 / 15

Bottleneck $= \min(10, 7, 9) = 7$ . Edge $A \to C$ (cap 7) is the bottleneck.

Step 4 / 15

Push 7 units. Update flow on each edge. $A \to C$ is now saturated (7/7).

Step 5 / 15

Iteration 2: BFS. $A \to C$ saturated, so BFS finds $S \to B \to D \to T$ .

Step 6 / 15

Bottleneck $= \min(8, 10, 12) = 8$ . Edge $S \to B$ (cap 8) is the bottleneck.

Step 7 / 15

Push 8 units. $S \to B$ saturated (8/8).

Step 8 / 15

Iteration 3: $S \to B$ saturated. Only $S \to A$ (residual $10-7=3$ ) leaves $S$ . BFS: $S \to A \to B \to D \to T$ .

Step 9 / 15

Residual: $S \to A$ : 3, $A \to B$ : 5, $B \to D$ : 2, $D \to T$ : 4. Bottleneck $= 2$ at $B \to D$ .

Step 10 / 15

Push 2 units. $B \to D$ now saturated (10/10).

Step 11 / 15

Iteration 4: $S \to A$ has 1 residual. $A \to C$ saturated, $A \to B$ has 3. But $B \to D$ saturated — dead end via $B$ . Need residual graph: reverse edge $C \to A$ has 7 capacity (undo $A \to C$ flow).

Step 12 / 15

Residual path found: $S \to A$ (1) $\to$ reverse $A \to C$ (7) $\to C \to D$ (3) $\to D \to T$ (2). Bottleneck $= \min(1,7,3,2) = 1$ .

Step 13 / 15

Push 1 unit via residual. $A \to C$ flow decreases $7 \to 6$ (reverse edge used). $S \to A$ : 10/10 (saturated!). Total $= 18$ .

Step 14 / 15

No more paths: $S \to A$ (10/10) and $S \to B$ (8/8) both saturated. BFS from $S$ finds nothing. Algorithm terminates.

Step 15 / 15

Result: Max flow $= 18$ . Min-cut: $\{S\}$ vs $\{A,B,C,D,T\}$ , capacity $10+8 = 18$ .

Key Insight: Residual Graph

The residual graph includes:

Forward edges: remaining capacity

= c(u,v) - f(u,v)

Reverse edges: allow “undoing” flow

= f(u,v)

Iteration 4 used a reverse edge to reroute:

A \to C

flow decreased from 7 to 6, redirecting 1 unit through

C \to D \to T

Complexity

Edmonds-Karp (BFS):

O(VE^2)

Dinic's:

O(V^2 E)

— standard for competitive programming

Push-Relabel:

O(V^2 E)

O(V^3)

Implementation (Dinic's)

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):
        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, f):
        if u == t:
            return f
        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(f, 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):
            self.iter = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f
        return flow