Edmonds-Karp Algorithm

Edmonds-Karp is Ford-Fulkerson with BFS used to select augmenting paths. By always choosing a shortest augmenting path (fewest edges), the algorithm achieves polynomial running time: $O(|V| \cdot |E|^2)$ regardless of capacity values.

Motivation

Ford-Fulkerson with arbitrary path selection can be pseudopolynomial ($O(|E| \cdot |f^*|)$), which is exponential in the input size (since capacities are represented in binary). Edmonds-Karp removes this dependency by guaranteeing a polynomial bound on the number of augmentations.

Algorithm

EDMONDS-KARP(G, s, t):
    initialise flow f = 0 on all edges
    while BFS from s finds a path p to t in G_f:
        c_f(p) = min{ c_f(u, v) | (u, v) on p }
        for each edge (u, v) on p:
            if (u, v) in G.E:
                f(u, v) = f(u, v) + c_f(p)
            else:
                f(v, u) = f(v, u) - c_f(p)
    return f

The only difference from Ford-Fulkerson is the use of BFS to find augmenting paths. Since all residual edges have weight 1 (we care about hop count), BFS naturally finds shortest paths.

Analysis

Let $\delta_f(s, v)$ be the shortest-path distance (in edges) from $s$ to $v$ in $G_f$.

Lemma 1 (Monotonicity): For every vertex $v \in V$, $\delta_f(s, v)$ is non-decreasing as the algorithm progresses. Proof: when we augment along a shortest path, we saturate bottleneck edges (removing them from $G_f$) and add reverse edges. Any new path through a reverse edge is strictly longer, so distances never decrease.

Lemma 2 (Edge saturations): Each edge can be saturated at most $|V|/2$ times. An edge is saturated when it lies on a shortest augmenting path. After saturation, to be used again, flow must be pushed back through the reverse edge, which requires the distance from $s$ to increase. Since distances are bounded by $|V|$, each edge saturates $O(|V|)$ times.

Total bound: There are $O(|V| \cdot |E|)$ augmentations. Each BFS costs $O(|E|)$. Total: $O(|V| \cdot |E|^2)$.

Comparison with Dinic

Dinic’s algorithm improves on Edmonds-Karp by finding multiple augmenting paths in a single BFS round using blocking flows. Running time: $O(|V|^2 \cdot |E|)$. Dinic is preferred in practice but Edmonds-Karp is the examinable variant. For bipartite matching networks, Edmonds-Karp (equivalently the Hopcroft-Karp analysis) yields $O(|E| \cdot \sqrt{|V|})$.

Worked Example

Consider the “bad case” for arbitrary-path Ford-Fulkerson:

s ---M--> a ---1--> b ---M--> t
|         |                  ^
+----M--->b----1--->a--------+

Where $M$ is a large integer. With DFS path selection alternating between $s \to a \to b \to t$ and $s \to b \to a \to t$, each augmentation increases flow by 1 (bottleneck is the capacity-1 cross edges), requiring $2M$ augmentations. Edmonds-Karp finds $s \to a \to b \to t$ (length 3) and augments by 1, then finds $s \to b \to a \to t$ (length 3), but because it always picks the shortest path, it still requires $O(M)$ augmentations in the worst case for this specific graph.

However, the polynomial bound $O(|V| \cdot |E|^2)$ is independent of $M$: here $|V| = 4$, $|E| = 5$, so $O(4 \cdot 25) = O(100)$ bound holds, though the actual $|f^*| = 2M$ could be much larger. The bound is a guarantee, not a tight estimate.

Summary

Aspect	Detail
Path selection	BFS (shortest by edge count)
Running time	$O(\lvert V \rvert \cdot \lvert E \rvert^2)$
Key lemma	$\delta_f(s, v)$ non-decreasing over augmentations
Edge saturations	$\le \lvert V \rvert / 2$ per edge
Compared to FF	Polynomial, independent of capacity magnitudes

Past Tripos: y2024p1q9, y2023p2q7.