Edmonds-Karp

Ford-Fulkerson is a method, not an algorithm — it just says "find augmenting paths until none exist" without specifying how to find them. With DFS you might get lucky, or you might spin forever on bad paths.

Edmonds-Karp makes one simple, powerful change: use BFS to always find the shortest augmenting path (fewest edges). That's it. One line different. But it gives you a polynomial worst-case guarantee no matter what the capacities are.

Why DFS Can Be Terrible

Picture two paths from s to t: one through a narrow bridge with capacity 1, another around it with capacity 1,000,000. With DFS, you might alternate between these two paths forever, sending just 1 unit each time. After 2,000,000 iterations, you've finished what BFS would have done in two steps.

With irrational capacities, DFS-based Ford-Fulkerson can even fail to terminate — oscillating without converging to the correct answer.

BFS Saves the Day: The Monotonicity Argument

When you always augment along the shortest path (by number of edges), augmenting path lengths can only stay the same or increase — they never decrease. This monotonicity is the key to the polynomial bound.

Here's why it matters: once a path of length L is used repeatedly, eventually its bottleneck edge gets saturated and removed. That edge might come back via a backward edge later — but only as part of a longer path. Since path lengths are bounded by V, the total number of augmentations is bounded.

The \(O(VE^2)\) Proof Sketch

Each edge can become a bottleneck at most \(O(V)\) times before the shortest path length increases past it. There are E edges. So: \(O(V)\) bottleneck events per edge × E edges = \(O(VE)\) total augmentations. Each augmentation runs one BFS costing \(O(E)\). Total: \(O(VE)\) × \(O(E)\) = \(O(VE^2)\).

This is independent of the maximum flow value — a true polynomial bound in graph size, not flow magnitude.

Implementation

The only difference from a basic Ford-Fulkerson is using a queue (BFS) instead of a stack/recursion (DFS) to find augmenting paths. Residual graph management is identical: for each edge (u→v), store both forward capacity and backward capacity as a pair.

Edmonds-Karp

from collections import deque

def edmonds_karp(cap, s, t):
    n = len(cap)
    total = 0

    while True:
        # BFS for shortest augmenting path
        parent = [-1] * n
        parent[s] = s
        q = deque([s])
        while q and parent[t] < 0:
            u = q.popleft()
            for v in range(n):
                if parent[v] < 0 and cap[u][v] > 0:
                    parent[v] = u
                    q.append(v)
        if parent[t] < 0:
            break

        # Bottleneck
        path_flow = float('inf')
        v = t
        while v != s:
            u = parent[v]
            path_flow = min(path_flow, cap[u][v])
            v = u

        # Update residual
        v = t
        while v != s:
            u = parent[v]
            cap[u][v] -= path_flow
            cap[v][u] += path_flow
            v = u
        total += path_flow

    return total

# Example network
cap = [
    [0, 10, 10, 0,  0,  0],
    [0,  0,  0, 5,  0,  0],
    [0,  0,  0, 0, 10,  0],
    [0,  0,  0, 0,  5, 10],
    [0,  0,  0, 0,  0, 10],
    [0,  0,  0, 0,  0,  0],
]
print(edmonds_karp(cap, 0, 5))  # 15

Output

Complexity

⏱️ Total time

\(O(VE)\) augmentations × \(O(E)\) per BFS; much better than \(O(E·|f|)\) when flow is large

Polynomial — independent of flow magnitude \(O(VE^2)\)

🔄 Number of augmentations

Each edge becomes a bottleneck at most \(O(V)\) times before the shortest path length grows

At most V×E rounds \(O(VE)\)

🔍 Each BFS

Standard BFS finds shortest augmenting path by edge count

Linear in edges \(O(E)\)

⚡ vs Dinic's Algorithm

Dinic's sends entire blocking flows per BFS phase — many paths at once instead of one

Slower for large sparse graphs \(O(VE^2)\) vs \(O(V^2E)\)

Why DFS Can Be Terrible

BFS Saves the Day: The Monotonicity Argument

The \(O(VE^2)\) Proof Sketch

Implementation

Edmonds-Karp

Complexity

Quick check