vault

Edmonds-Karp

14 min read

Edmonds-Karp

Edmonds-Karp is the Ford-Fulkerson method specialized so that each augmenting path is the shortest (in terms of edge count) path from source to sink in the residual graph, found by Breadth-First Search. This single design choice fixes two flaws of generic Ford-Fulkerson at once: (1) it eliminates the dependence of the running time on the maximum-flow value, giving a guaranteed O(V · E²) regardless of capacities, and (2) it terminates correctly on graphs with irrational capacities, where naive depth-first augmenting can fail to converge. The algorithm was published by Edmonds & Karp in 1972, but the same O(V · E²) bound for the BFS-shortest-path variant had been independently discovered by Dinitz (often anglicized “Dinic”) in 1970 — a fact that has caused decades of name confusion. Edmonds-Karp is the algorithm interviewers expect when they say “implement max flow”; it is also the natural first stop on the road to the asymptotically faster Dinic’s Algorithm.

1. Intuition — Why “Shortest” Helps

The root inefficiency of generic Ford-Fulkerson is that bad path choices can waste effort. A pathological example: capacities of 10^9 on most edges and a single bottleneck edge of capacity 1 between two intermediate vertices. A depth-first search may keep choosing paths that traverse the bottleneck, each pushing only 1 unit, requiring 2·10^9 iterations even though the optimal flow is achievable in two pushes. The dependency on |f*| (max-flow value) makes the algorithm pseudopolynomial — fast in problem-graph terms but exponential in input bit-length when capacities are large.

Edmonds-Karp’s insight is structural rather than capacity-driven. By always augmenting along a shortest s → t path in the current residual graph, two invariants hold across iterations:

  1. The distance from s to any vertex v in the residual graph is non-decreasing as the algorithm progresses. Once a vertex is “k hops away from s,” it stays at least k hops away forever.
  2. Each edge can become “saturated” (its forward residual hits zero, removing it from the residual graph) at most O(V) times — because each saturation requires the distance to its tail vertex to strictly increase, and that distance can only grow up to V.

Multiplying these together: each of the O(E) edges is saturated at most O(V) times, and each saturation corresponds to at most one augmenting iteration with that edge as bottleneck, so the total number of augmenting iterations is O(V · E). Each iteration costs O(E) for the BFS, giving O(V · E²). Crucially, none of this depends on capacity values — the analysis is purely combinatorial. That’s the magic.

The “explain to a child” version: imagine the network as a multi-day flood evacuation. Every day, you rescue people along the shortest available route. Each road can only get blocked finitely many times, because every time it gets unblocked-and-reused you’ve had to restructure the road network, and you can’t keep restructuring forever — there are only so many possible “shapes” of road. So the total number of evacuation days is bounded, regardless of how many people each truck carries.

2. The Algorithm

edmonds_karp(G, s, t):
    initialize f(u, v) := 0 for all (u, v)
    while True:
        path := bfs_shortest_path_in_residual_graph(s, t)
        if path is empty:
            return total flow
        b := bottleneck capacity of path
        push b along path (update forward and reverse residuals)
        total flow += b

The only difference from the generic Ford-Fulkerson template (see Maximum Flow §3) is the augmenting-path choice: BFS is mandatory, not optional. BFS visits vertices in increasing order of edge-count distance from s, so the first time we pop t we have the shortest such path.

3. Tiny Worked Example

Consider a 4-vertex network demonstrating where Edmonds-Karp visibly beats DFS-based augmenting. Edges:

s → a : 1000
s → b : 1000
a → b :    1
a → t : 1000
b → t : 1000

Maximum flow is 2000 (push 1000 along s→a→t, 1000 along s→b→t).

DFS-based Ford-Fulkerson, worst case:

If DFS happens to follow s → a → b → t first (using edge a→b), bottleneck is 1, push 1. Now reverse residual b → a is 1. Next iteration, DFS finds s → b → a → t (using the reverse of a→b), bottleneck 1, push 1. Continuing, DFS oscillates between forward and reverse uses of edge a→b, each iteration pushing 1, taking 2000 iterations to converge.

Edmonds-Karp (BFS):

BFS from s finds the shortest path. From s, we can reach a and b in one hop, and t in two hops via s→a→t or s→b→t (length 2). Path s→a→b→t is length 3, longer, so BFS will not pick it. Iteration 1: pick s→a→t, bottleneck 1000, push 1000. Iteration 2: pick s→b→t, bottleneck 1000, push 1000. Iteration 3: BFS finds no s→t path of positive residual edges (the only remaining residual s→t route goes through the awkward a→b edge of capacity 1, and even that has been disconnected from t because a→t and b→t are saturated). Done in 2 iterations.

The ratio 2000 / 2 = 1000 reflects exactly the capacity disparity that DFS-based augmenting amplifies and BFS sidesteps.

4. Pseudocode

edmonds_karp(G, s, t):
    initialize residual graph G_f from G
    total := 0
    while True:
        # BFS in G_f, recording parent pointers
        parent := { s: None }
        queue := [s]
        while queue not empty and t not in parent:
            u := dequeue
            for v with c_f(u, v) > 0 and v not in parent:
                parent[v] := u
                enqueue v
        if t not in parent:
            return total                       # no augmenting path → done
        # reconstruct path and find bottleneck
        b := ∞
        v := t
        while parent[v] is not None:
            u := parent[v]
            b := min(b, c_f(u, v))
            v := u
        # augment along path
        v := t
        while parent[v] is not None:
            u := parent[v]
            c_f(u, v) -= b
            c_f(v, u) += b
            v := u
        total := total + b

5. Python Implementation

from collections import defaultdict, deque
 
def edmonds_karp(edges, s, t):
    """edges: list of (u, v, capacity). Returns max flow value from s to t."""
    # build residual: dict-of-dicts so residual[u][v] is the capacity left
    cap = defaultdict(lambda: defaultdict(int))
    nodes = {s, t}
    for u, v, c in edges:
        cap[u][v] += c
        cap[v][u] += 0          # ensure key exists (no-op default)
        nodes.update([u, v])
    total = 0
    while True:
        # BFS for shortest residual path
        parent = {s: None}
        q = deque([s])
        while q and t not in parent:
            u = q.popleft()
            for v, c in cap[u].items():
                if c > 0 and v not in parent:
                    parent[v] = u
                    if v == t:
                        break
                    q.append(v)
        if t not in parent:
            return total
        # find bottleneck along reconstructed path
        b, v = float('inf'), t
        while parent[v] is not None:
            u = parent[v]
            b = min(b, cap[u][v])
            v = u
        # augment
        v = t
        while parent[v] is not None:
            u = parent[v]
            cap[u][v] -= b
            cap[v][u] += b
            v = u
        total += b

Implementation notes.

  • We dictionary-encode the residual graph because in interview settings vertex labels are often strings, and the cleanest data structure is cap[u][v]. For numerical-vertex hot-loop production code, replace with cap = [[0] * n for _ in range(n)] (an adjacency matrix) plus an adjacency list.
  • The BFS records parent[v] = u only when first discovering v; this guarantees parent chains form a shortest-path tree.
  • The early break when reaching t is an optimization — once we’ve found t, we don’t need to keep BFSing.
  • The augment loop walks parent pointers from t back to s twice (once to find bottleneck, once to apply it). You can fuse them into one pass by storing per-edge references along the path, but the two-pass version is more readable and asymptotically identical.

6. Complexity Analysis

Theorem (Edmonds & Karp, 1972). Edmonds-Karp computes the maximum flow in O(V · E²) time, regardless of edge capacities (including irrational ones).

The proof is one of the classic combinatorial arguments in algorithms; it’s worth understanding rather than just memorizing.

6.1 Lemma 1 — Distances are monotone

Let d_f(s, v) denote the BFS-distance (in number of edges) from s to v in the residual graph after some flow f. Augmenting along a shortest residual path produces a new flow f'; we claim d_{f'}(s, v) ≥ d_f(s, v) for every v.

Proof sketch. Suppose for contradiction that some vertex v becomes closer to s in G_{f'} than in G_f. Pick v to be the closest such vertex (i.e., minimum d_{f'}(s, v)). Consider the shortest path from s to v in G_{f'}; let u be the predecessor of v on this path. By choice of v as the closest violator, d_{f'}(s, u) ≥ d_f(s, u). Now examine the edge (u, v):

  • Case A: (u, v) exists in G_f. Then d_f(s, v) ≤ d_f(s, u) + 1 ≤ d_{f'}(s, u) + 1 = d_{f'}(s, v), contradicting our assumption.
  • Case B: (u, v) exists in G_{f'} but not in G_f. This means the augmenting path used edge (v, u) (in that direction), creating reverse residual (u, v). Since augmentation was along a shortest path in G_f, edge (v, u) lies on a shortest path, so d_f(s, u) = d_f(s, v) + 1, i.e., d_f(s, v) = d_f(s, u) − 1 ≤ d_{f'}(s, u) − 1 = d_{f'}(s, v) − 2 < d_{f'}(s, v). Again contradicting the assumption.

Both cases contradict, so no such v exists. □

6.2 Lemma 2 — Each edge is saturated O(V) times

When an edge (u, v) becomes “critical” (its residual capacity drops to zero on some augmenting path), the path used has the form s → ⋯ → u → v → ⋯ → t of length d_f(s, u) + 1 + d_f(v, t) = d_f(s, t) since it’s a shortest path. After augmentation, (u, v) disappears from the residual graph until some future augmenting path uses the reverse edge (v, u). When that happens, that future path has the form s → ⋯ → v → u → ⋯ → t, so d_{f'}(s, u) = d_{f'}(s, v) + 1. Combined with Lemma 1 (d_{f'}(s, v) ≥ d_f(s, v) = d_f(s, u) + 1), we get d_{f'}(s, u) ≥ d_f(s, u) + 2.

So between successive saturations of the same edge (u, v), the distance d(s, u) strictly increases by at least 2. Since distances are bounded above by V − 1 (the longest possible simple path), each edge can be saturated at most O(V) times.

6.3 Putting it together

There are O(E) distinct edges in the residual graph. Each is saturated at most O(V) times. Each augmenting iteration saturates at least one edge (the bottleneck). Therefore, the number of augmenting iterations is O(V · E). Each iteration runs a BFS in O(V + E) = O(E) and does a path walk in O(V) ≤ O(E). Total: O(V · E · E) = O(V · E²). □

6.4 Practical caveats

  • O(V · E²) is the worst case; on most inputs Edmonds-Karp finishes far faster.
  • For dense graphs (E = Θ(V²)), the bound becomes O(V⁵), which is poor. Switch to Dinic’s Algorithm for O(V²·E) or push-relabel for O(V²·√E).
  • For unit-capacity graphs (every capacity is 0 or 1, common in Bipartite Matching), Edmonds-Karp is O(E·√V) if you specifically use Dinic’s blocking-flow refinement; pure Edmonds-Karp is O(V·E) on unit-capacity graphs, still fine but not optimal.

7. Variants and Connections

7.1 Choosing BFS vs other strategies

  • BFS (Edmonds-Karp): simplest with provable polynomial guarantees. Default for interviews.
  • Fattest path (Edmonds-Karp 1972 also analyzed this): at each step, find the path with maximum bottleneck (using a Dijkstra-like priority queue with max-min semantics). Iterations: O(E · log U) where U is the max capacity. Often faster in practice but algorithmically more complex.
  • Capacity scaling: binary-search the threshold; only consider edges with residual capacity ≥ threshold; halve threshold. Iterations: O(E · log U).
  • Level graph + blocking flow: Dinic’s Algorithm. Asymptotically better.

7.2 Why Edmonds-Karp is the “standard” interview answer

Compared to push-relabel and Dinic’s, Edmonds-Karp:

  • Has the simplest implementation (BFS + adjacency-map updates)
  • Has an elegant, teachable correctness/complexity proof
  • Uses only ideas already in the interviewer’s working memory (Breadth-First Search + residual graph + augmenting path)
  • Is rarely the bottleneck — most interview problems with max-flow flavor have small enough graphs that O(V·E²) is plenty

If the interviewer presses for asymptotic improvements, mention Dinic’s or push-relabel; otherwise stick with Edmonds-Karp.

8. Common Interview Problems

ProblemHow Edmonds-Karp applies
LC 1947 — Maximum Compatibility Score SumReduce to bipartite-matching-with-weights → max-flow / Hungarian
LC 1820 — Maximum Number of Accepted InvitationsBipartite matching → unit-capacity max-flow
LC 1349 — Maximum Students Taking ExamBipartite matching on grid (often DP, but max-flow is valid)
Classic: maximum bipartite matchingSee Bipartite Matching
Classic: edge-disjoint pathsSet every capacity to 1; max flow counts disjoint paths
Classic: minimum cut between two citiesRun max-flow, then identify residual-graph reachable set from s
Classic: project selectionReduce profit-maximization to min-cut
Classic: image segmentation (graph cut)s = “foreground source”, t = “background sink”; min-cut partitions

9. Pitfalls

9.1 Using DFS by accident

Trivially silently breaks the complexity guarantee. Test: print the number of augmenting iterations on a contrived high-capacity graph; if it’s proportional to |f*|, you’re using DFS.

9.2 BFS that doesn’t respect residual capacity

The neighbor expansion must check c_f(u, v) > 0, not whether (u, v) is an edge in the original graph. Many bugs trace to BFSing over the original adjacency list and then failing to find paths that pass through reverse edges.

9.3 Updating residuals only in one direction

After augmenting, both c_f(u, v) -= b and c_f(v, u) += b must occur. Forgetting either is a silent correctness bug.

9.4 Repeatedly recreating data structures

Each iteration creates a new parent map and a new BFS queue — this is correct. But pre-allocating a single mutable parent array and clearing it between iterations is significantly faster on dense graphs. For interviews, idiomatic per-iteration construction is fine.

9.5 Believing the algorithm “doesn’t work” on irrational capacities

Edmonds-Karp’s O(V·E²) bound is combinatorial and does not reference capacity values. It works correctly on any rational, irrational, or integer capacity. The only constraint is that arithmetic on capacities must be exact — which means floating-point capacities will give floating-point flows, and rounding errors can cause weird behavior. Use rationals or scaled integers in production.

9.6 Not handling disconnected graphs

If t is unreachable from s in the original graph, Edmonds-Karp’s first BFS finds no path and immediately returns 0. Correct, but worth confirming on test inputs.

9.7 Confusing “shortest path” with “fewest hops” vs “min-weight path”

In Edmonds-Karp, “shortest” specifically means fewest residual edges. It is not the path of minimum capacity sum, nor the fattest (max-min) path. Substituting Dijkstra-on-capacity for BFS does not give Edmonds-Karp’s bound — it gives a different (also-valid) algorithm with different complexity.

10. Diagram — Edmonds-Karp at Work

flowchart LR
  s((s)) -->|10| a((a))
  s -->|10| b((b))
  a -->|5|  t((t))
  a -->|1|  b
  b -->|10| t

  classDef visited fill:#bef,stroke:#06c,color:#000;
  class s,a,b,t visited;

What this diagram shows. The original capacity graph used in §4 of Maximum Flow. Edmonds-Karp’s BFS from s reaches a and b at distance 1, and reaches t at distance 2 via s→a→t or s→b→t. The path s→a→b→t is at distance 3 and is never chosen until iterations after the shorter paths are saturated. This selection discipline is precisely what bounds the iteration count to O(V · E) regardless of how large the numerical capacities are.

11. Open Questions

  • Why don’t we use the fattest-path strategy in practice if it’s also O(E · log U) per iteration with a similar total bound? (In practice, BFS is much simpler to code and the constant factor on the priority queue dominates for small U.)
  • Is there a simple proof that Edmonds-Karp’s bound is tight? (Yes: a sequence of “zigzag” graphs achieves Θ(V · E²) on adversarial inputs; see Galil 1980 for an explicit construction.)
  • How does Edmonds-Karp parallelize? (Poorly. The augmenting-path framework is inherently sequential. Push-relabel is the parallel-friendly choice.)

12. See Also

Graph View

Backlinks