Edmonds-Karp

How Edmonds-Karp works

The maximum flow problem asks: given a directed graph with edge capacities and a designated source s and sink t, how much flow can you push from s to t without exceeding any edge's capacity? Ford and Fulkerson gave the answer in 1956 with the augmenting-path method:

1. Initialize flow to zero on every edge.
2. Find any path from s to t in the residual graph — the graph showing remaining capacity (forward) and possible cancellations (reverse).
3. Push as much flow as possible along that path (bottleneck capacity).
4. Repeat. Stop when no augmenting path exists.

The catch: step 2 says "any path" — and bad choices can spiral. With integer capacities up to U, naive Ford-Fulkerson can run for U iterations. With irrational capacities, it might never terminate. Edmonds and Karp fixed this in 1972 with a single swap: always pick the shortest augmenting path (by edge count) — use BFS.

That one rule converts an unbounded algorithm into a guaranteed O(VE²) polynomial procedure, completely independent of capacities. Their proof is elegant: the length of the shortest augmenting path never decreases, and each edge can be the bottleneck of at most V/2 different shortest paths, so total augmentations are O(VE); each BFS is O(E); total O(VE²).

The residual graph

This is the trick that makes augmenting paths work. After pushing f units along edge (u, v) with capacity c, the residual graph has:

forward edge (u, v) with residual capacity c − f
reverse edge (v, u) with residual capacity f

The reverse edge says: "I can undo up to f units of flow that's currently on (u, v)." Without it, an early greedy choice could lock the algorithm into a suboptimal answer. With it, later augmenting paths can reroute flow through the reverse edge — effectively cancelling and rerouting in one go. This is how Edmonds-Karp recovers from bad early decisions.

Walk-through example

Capacities:
  s → A (10)   s → B (10)
  A → C (4)    A → D (8)
  B → C (9)
  C → t (10)   D → t (10)

Iteration 1 — BFS finds shortest path s → A → C → t (length 3)
  Bottleneck = min(10, 4, 10) = 4
  Push 4. Residuals update: (s,A)=6, (A,C)=0, (C,t)=6, reverses appear.

Iteration 2 — BFS finds s → A → D → t (length 3)
  Bottleneck = min(6, 8, 10) = 6
  Push 6. (s,A)=0, (A,D)=2, (D,t)=4.

Iteration 3 — BFS finds s → B → C → t (length 3)
  Bottleneck = min(10, 9, 6) = 6
  Push 6. (s,B)=4, (B,C)=3, (C,t)=0.

Iteration 4 — BFS from s can reach A (via s→B→C→A reverse), but
  no path reaches t. Algorithm terminates.

Max flow = 4 + 6 + 6 = 16.

Three augmenting paths, each found by BFS in O(E) time. The shortest-path discipline ensured the algorithm couldn't dawdle on suboptimal long paths.

Edmonds-Karp vs Ford-Fulkerson vs Dinic

	Ford-Fulkerson	Edmonds-Karp	Dinic	Push-Relabel
Path selection	Any augmenting path	BFS shortest path	BFS layered graph, blocking flow	No paths — local pushes
Worst-case time	O(E · max-flow)	O(VE²)	O(V²E)	O(V²√E) or O(V²E)
Polynomial?	Only for integer capacities	Always	Always	Always
Unit capacities	O(E · max-flow)	O(VE²)	O(E√V)	O(E√V) (with FIFO)
Code complexity	~25 lines	~30 lines (Ford-Fulkerson + BFS)	~80 lines (layered)	~150 lines (heights + excess)
Production solvers	—	Teaching	OR-Tools, LEMON	Boost Graph, HIPR
Original paper	Ford-Fulkerson 1956	Edmonds-Karp 1972	Dinitz 1970	Goldberg-Tarjan 1988

For dense graphs, Dinic and push-relabel are practically faster. For sparse graphs of moderate size, Edmonds-Karp is competitive and far easier to debug. For 99% of textbook and interview situations, Edmonds-Karp is the right balance between rigor and simplicity. See Ford-Fulkerson for the parent scheme.

Pseudo-code

// Adjacency lists with residual capacities residual[u][v].

edmonds_karp(graph, s, t):
    flow = 0
    while true:
        // BFS for an augmenting path
        parent = dict()
        parent[s] = s
        queue = [s]
        while queue not empty and t not in parent:
            u = queue.pop_front()
            for v in graph.neighbors(u):
                if v not in parent and residual[u][v] > 0:
                    parent[v] = u
                    queue.push_back(v)

        if t not in parent: return flow   // no path → done

        // bottleneck capacity along the path
        bottleneck = +∞
        v = t
        while v != s:
            u = parent[v]
            bottleneck = min(bottleneck, residual[u][v])
            v = u

        // augment
        v = t
        while v != s:
            u = parent[v]
            residual[u][v] -= bottleneck
            residual[v][u] += bottleneck
            v = u

        flow += bottleneck

Python implementation

from collections import defaultdict, deque

def edmonds_karp(n, capacities, source, sink):
    """capacities: list of (u, v, c) directed edges."""
    res = defaultdict(lambda: defaultdict(int))
    for u, v, c in capacities:
        res[u][v] += c   # accumulate parallel edges

    flow = 0
    while True:
        parent = {source: source}
        q = deque([source])
        while q and sink not in parent:
            u = q.popleft()
            for v, c in res[u].items():
                if v not in parent and c > 0:
                    parent[v] = u
                    q.append(v)
        if sink not in parent:
            break

        # find bottleneck
        bn = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            bn = min(bn, res[u][v])
            v = u

        # augment
        v = sink
        while v != source:
            u = parent[v]
            res[u][v] -= bn
            res[v][u] += bn
            v = u
        flow += bn

    return flow

# Example
edges = [
    ('s', 'A', 10), ('s', 'B', 10),
    ('A', 'C', 4),  ('A', 'D', 8),
    ('B', 'C', 9),
    ('C', 't', 10), ('D', 't', 10),
]
print(edmonds_karp(6, edges, 's', 't'))  # 16

JavaScript implementation

function edmondsKarp(n, edges, source, sink) {
  // residual[u] = Map(v -> capacity)
  const res = Array.from({ length: n }, () => new Map());
  for (const [u, v, c] of edges) {
    res[u].set(v, (res[u].get(v) || 0) + c);
    if (!res[v].has(u)) res[v].set(u, 0);
  }

  let flow = 0;
  while (true) {
    // BFS
    const parent = new Array(n).fill(-1); parent[source] = source;
    const q = [source];
    while (q.length && parent[sink] === -1) {
      const u = q.shift();
      for (const [v, c] of res[u]) {
        if (parent[v] === -1 && c > 0) { parent[v] = u; q.push(v); }
      }
    }
    if (parent[sink] === -1) break;

    let bn = Infinity;
    for (let v = sink; v !== source; v = parent[v]) {
      bn = Math.min(bn, res[parent[v]].get(v));
    }
    for (let v = sink; v !== source; v = parent[v]) {
      const u = parent[v];
      res[u].set(v, res[u].get(v) - bn);
      res[v].set(u, (res[v].get(u) || 0) + bn);
    }
    flow += bn;
  }
  return flow;
}

When to use Edmonds-Karp

• Teaching and prototyping. Roughly 30 lines, easy to step through in a debugger. If you suspect a max-flow bug, Edmonds-Karp's per-iteration trace is the ground truth.
• Small-to-medium networks. Up to a few thousand nodes / tens of thousands of edges, Edmonds-Karp finishes in milliseconds — fast enough for many production tasks.
• Bipartite matching (theoretical). Max flow on a unit-capacity bipartite graph computes maximum matching. Edmonds-Karp gives O(VE²) here, but Hopcroft-Karp is much faster — see Hopcroft-Karp.
• Image segmentation (small images). Foreground/background segmentation via min-cut. For real images, Boykov-Kolmogorov's variant is dramatically faster, but Edmonds-Karp works for thumbnails.
• Project selection / baseball elimination. Classic reductions where the graph is small but the modeling is the hard part — Edmonds-Karp's simplicity matters more than its speed.

Common pitfalls

• Forgetting reverse edges. The most common bug. Without reverse-edge residuals, the algorithm can lock into suboptimal flows. Always initialize residual[v][u] = 0 for every forward edge (u, v).
• Using DFS instead of BFS. DFS is fine for correctness (still Ford-Fulkerson) but loses the O(VE²) guarantee. For weighted graphs with integer capacities, DFS-based augmentation can run for capacity-many iterations.
• Parallel edges. Two edges from u to v with capacities 5 and 3 collapse into one edge of capacity 8 in most implementations. Be careful if your graph distinguishes them for any reason.
• Floating-point capacities. Edmonds-Karp's bound applies for any capacities, but with floats you can lose precision over many augmentations. For exact answers use integers (scaling, rationals, big-int).
• Wrong answer on disconnected graphs. If no path from s to t exists at all, max flow is 0 — the algorithm correctly returns 0, but double-check that s ≠ t and that both exist in the graph.
• Modifying the original graph. Build the residual graph as a separate structure; modifying the input is a frequent source of bugs and side effects in shared code.

Performance analysis

BFS per iteration: O(V + E), or just O(E) for connected graphs. Number of augmentations is bounded by O(VE) via Edmonds-Karp's monotone-distance argument. Total time: O(VE²).

Numbers from real graphs:

• V = 100, E = 500 (sparse): roughly 100 × 500² = 2.5 × 10⁷ ops — <1 ms in Python.
• V = 1000, E = 10000 (sparse): 10¹¹ ops — ~30 s in Python, much less in C++.
• V = 10000, E = 100000 (web-scale graphs): 10¹⁴ ops — impractical. Use Dinic or push-relabel.

Memory: residual graph dominates at O(V + E). For each forward edge you store a reverse edge → memory doubles, but stays linear in the input.

Max-flow min-cut

The truly beautiful corollary: when Edmonds-Karp terminates, the BFS from s in the final residual graph reaches some set of vertices S that does NOT contain t. The set of original edges crossing the cut (S, V \ S) is an s-t cut, and its total capacity equals the computed max flow. This is the celebrated max-flow min-cut theorem: the value of the maximum flow always equals the capacity of the minimum cut.

So the algorithm doesn't just compute max flow — it implicitly identifies the bottleneck edges (the min cut), which is often the more important answer in applications (where's the bottleneck in our pipeline?). Same algorithm, two answers.