Algorithm Deep Dive: Edmonds-Karp Algorithm

A Bit of History

In 1972, Jack Edmonds (already met via the Chu-Liu/Edmonds algorithm in Part 11) and Richard Karp (of Held-Karp and soon Hopcroft-Karp) published "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems," proving that simply choosing the shortest augmenting path (via BFS) at every step guarantees polynomial time, fixing the pathological slowness the Ford-Fulkerson deep dive described. What Edmonds and Karp couldn't have known: two years earlier, in 1970, Soviet computer scientist Yefim (Efim) Dinitz had already discovered essentially the same idea — and a more sophisticated "blocking flow" algorithm besides — publishing it in a Soviet journal. Cold War-era restrictions on scientific communication meant neither research group learned of the other's work for years; the algorithm is now credited to both, sometimes explicitly written "Edmonds-Karp (independently, Dinitz)" in careful modern references.

Working Principle

Edmonds-Karp is Ford-Fulkerson with exactly one change: the augmenting path is always found via BFS (guaranteeing the shortest, in edge count, augmenting path available in the current residual graph), rather than an arbitrary DFS or unspecified search. Every other part of the algorithm — pushing bottleneck flow, updating residual capacities — is identical to Ford-Fulkerson.

Key Insight

This is a beautiful, minimal fix: the entire improvement over Ford-Fulkerson's worst-case behavior comes from swapping DFS for BFS in exactly the same augmenting-path search — nothing else about the method changes. It's a strong illustration of how much a seemingly small implementation choice (BFS vs. DFS) can affect worst-case guarantees, even when both choices produce a "correct" algorithm.

Why BFS Bounds the Iteration Count

The key lemma: the shortest-path distance from $s$ to any vertex $v$ in the residual graph is monotonically non-decreasing across successive augmentations — it never gets shorter as the algorithm progresses. Combined with a careful counting argument (each edge can be the "bottleneck" of an augmenting path at most $O(V)$ times before its distance from $s$ must strictly increase, and distances are bounded by $V$), this bounds the total number of augmentations at $O(VE)$ — a bound that depends only on the graph's size, not on capacity values at all, unlike plain Ford-Fulkerson.

Complexity Analysis

$O(VE)$ augmentations, each requiring an $O(E)$ BFS to find:

$$\text{Time: } O(VE^2) \qquad \text{Space: } O(V + E)$$

Crucially, this bound is strongly polynomial — independent of the actual capacity values, unlike Ford-Fulkerson's $O(EF)$ pseudo-polynomial bound from its own deep dive.

Implementation

from collections import defaultdict, deque

def edmonds_karp(capacity, source, sink):
    """capacity: dict[(u,v)] -> capacity (int). Returns max flow value."""
    residual = defaultdict(int)
    graph = defaultdict(set)
    for (u, v), cap in capacity.items():
        residual[(u, v)] += cap
        graph[u].add(v)
        graph[v].add(u)

    def bfs_augmenting_path():
        parent = {source: None}
        queue = deque([source])
        while queue:
            u = queue.popleft()
            if u == sink:
                return parent
            for v in graph[u]:
                if residual[(u, v)] > 0 and v not in parent:
                    parent[v] = u
                    queue.append(v)
        return None

    max_flow = 0
    while (parent := bfs_augmenting_path()):
        path = []
        v = sink
        while v is not None:
            path.append(v)
            v = parent[v]
        path.reverse()

        bottleneck = min(residual[(path[i], path[i+1])] for i in range(len(path) - 1))
        for i in range(len(path) - 1):
            u, v = path[i], path[i + 1]
            residual[(u, v)] -= bottleneck
            residual[(v, u)] += bottleneck

        max_flow += bottleneck

    return max_flow

capacity = {("S","A"): 3, ("S","B"): 2, ("A","T"): 2, ("B","T"): 3, ("A","B"): 1}
print(edmonds_karp(capacity, "S", "T"))   # 5 -- same answer, fewer/shorter-guided iterations

#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <climits>
#include <iostream>
using namespace std;

int edmondsKarp(unordered_map<string, unordered_map<string,int>>& residual,
                 unordered_map<string, unordered_set<string>>& graph,
                 string source, string sink) {
    int maxFlow = 0;

    while (true) {
        unordered_map<string, string> parent{{source, ""}};
        queue<string> q; q.push(source);
        bool found = false;

        while (!q.empty() && !found) {
            string u = q.front(); q.pop();
            if (u == sink) { found = true; break; }
            for (auto& v : graph[u]) {
                if (residual[u][v] > 0 && !parent.count(v)) {
                    parent[v] = u;
                    q.push(v);
                }
            }
        }
        if (!parent.count(sink)) break;

        vector<string> path;
        for (string v = sink; !v.empty(); v = parent[v]) path.push_back(v);
        int bottleneck = INT_MAX;
        for (size_t i = path.size() - 1; i > 0; i--)
            bottleneck = min(bottleneck, residual[path[i]][path[i-1]]);

        for (size_t i = path.size() - 1; i > 0; i--) {
            residual[path[i]][path[i-1]] -= bottleneck;
            residual[path[i-1]][path[i]] += bottleneck;
        }
        maxFlow += bottleneck;
    }
    return maxFlow;
}

int main() {
    unordered_map<string, unordered_map<string,int>> residual = {
        {"S", {{"A",3},{"B",2}}}, {"A", {{"T",2},{"B",1}}}, {"B", {{"T",3}}}
    };
    unordered_map<string, unordered_set<string>> graph = {
        {"S", {"A","B"}}, {"A", {"S","T","B"}}, {"B", {"S","A","T"}}, {"T", {"A","B"}}
    };
    cout << "Max flow: " << edmondsKarp(residual, graph, "S", "T") << endl;  // 5
    return 0;
}

import java.util.*;

class EdmondsKarp {
    static int maxFlow(Map<String, Map<String, Integer>> residual,
                        Map<String, Set<String>> graph, String source, String sink) {
        int flow = 0;

        while (true) {
            Map<String, String> parent = new HashMap<>();
            parent.put(source, null);
            Queue<String> queue = new LinkedList<>();
            queue.add(source);
            boolean found = false;

            while (!queue.isEmpty() && !found) {
                String u = queue.poll();
                if (u.equals(sink)) { found = true; break; }
                for (String v : graph.getOrDefault(u, Set.of())) {
                    if (residual.get(u).getOrDefault(v, 0) > 0 && !parent.containsKey(v)) {
                        parent.put(v, u);
                        queue.add(v);
                    }
                }
            }
            if (!parent.containsKey(sink)) break;

            List<String> path = new ArrayList<>();
            for (String v = sink; v != null; v = parent.get(v)) path.add(v);
            int bottleneck = Integer.MAX_VALUE;
            for (int i = path.size() - 1; i > 0; i--)
                bottleneck = Math.min(bottleneck, residual.get(path.get(i)).getOrDefault(path.get(i-1), 0));

            for (int i = path.size() - 1; i > 0; i--) {
                String u = path.get(i), v = path.get(i - 1);
                residual.get(u).merge(v, -bottleneck, Integer::sum);
                residual.computeIfAbsent(v, k -> new HashMap<>()).merge(u, bottleneck, Integer::sum);
            }
            flow += bottleneck;
        }
        return flow;
    }

    public static void main(String[] args) {
        Map<String, Map<String,Integer>> residual = new HashMap<>();
        residual.put("S", new HashMap<>(Map.of("A",3,"B",2)));
        residual.put("A", new HashMap<>(Map.of("T",2,"B",1)));
        residual.put("B", new HashMap<>(Map.of("T",3)));
        residual.put("T", new HashMap<>());

        Map<String, Set<String>> graph = Map.of(
            "S", Set.of("A","B"), "A", Set.of("S","T","B"),
            "B", Set.of("S","A","T"), "T", Set.of("A","B")
        );
        System.out.println("Max flow: " + maxFlow(residual, graph, "S", "T"));  // 5
    }
}

Real-World Applications

Case Study

Guaranteed-Time Network Provisioning

Wherever a max-flow computation needs a hard, predictable time bound regardless of capacity magnitudes — telecommunications bandwidth provisioning, real-time network reconfiguration in emergency-response systems — Edmonds-Karp's strongly polynomial $O(VE^2)$ guarantee is preferred over plain Ford-Fulkerson, precisely because the latter's runtime can depend unpredictably on capacity values that might be very large or unevenly distributed.

Network ProvisioningBandwidth Allocation

Exercises

Run Edmonds-Karp by hand on the Ford-Fulkerson deep dive's worked example, and confirm the augmenting paths chosen (by BFS) differ from the DFS-found ones there, while the final max flow value still matches.
Explain, in your own words, why "shortest augmenting path is non-decreasing across iterations" is enough to bound the total number of iterations at $O(VE)$.
Construct a small network where Ford-Fulkerson (using an adversarial DFS choice) would take noticeably more iterations than Edmonds-Karp on the same graph.
Challenge: Implement both Ford-Fulkerson (DFS) and Edmonds-Karp (BFS) side by side, instrument both to count iterations, and compare the counts on a graph specifically designed to be adversarial for DFS.

Limitations

Not the Fastest Known Max-Flow Algorithm

$O(VE^2)$ is a solid guarantee, but far from state of the art — Dinitz's own blocking-flow algorithm achieves $O(V^2E)$, and modern max-flow research (briefly previewed in Part 23) has pushed the bound to nearly linear time in some settings. Edmonds-Karp remains an excellent teaching and general-purpose choice, but production systems handling very large flow networks typically reach for faster, more specialized algorithms.

Cookie Consent

Edmonds-Karp Algorithm

Contents

A Bit of History

Working Principle

Key Insight

Why BFS Bounds the Iteration Count

Complexity Analysis

Implementation

Real-World Applications

Guaranteed-Time Network Provisioning

Exercises

Limitations

Not the Fastest Known Max-Flow Algorithm

Cookie Consent

Edmonds-Karp Algorithm

Contents

A Bit of History

Working Principle

Key Insight

Why BFS Bounds the Iteration Count

Complexity Analysis

Implementation

Real-World Applications

Guaranteed-Time Network Provisioning

Exercises

Limitations

Not the Fastest Known Max-Flow Algorithm

Related Deep Dives

Graph Theory Series

Ford-Fulkerson Method

Hopcroft-Karp Algorithm