Algorithm Deep Dive: Edmonds-Karp Algorithm

A Bit of History

In 1972, Jack Edmonds and Richard Karp published a polynomial analysis of the shortest-augmenting-path rule for network flow. Yefim Dinitz had independently published the same shortest-path idea in 1970 as part of work that also led to the faster blocking-flow algorithm now associated with his name. The important algorithmic lesson is timeless: a small change in selection order can transform a correct method with an unstable runtime into one with a graph-size guarantee.

From Ford–Fulkerson to Edmonds–Karp

Both methods maintain exactly the same residual network and perform exactly the same augmentation update. Only the path-selection rule changes.

Shared state

Residual capacities

Forward residual capacity permits more flow; reverse residual capacity permits cancelling earlier flow.

Shared update

Push the bottleneck

For path $P$, push $\Delta=\min_{(u,v)\in P}c_f(u,v)$ and update both directions.

New rule

Choose with BFS

Among all residual $s$–$t$ paths, use one with the fewest edges.

Ford–Fulkerson: any pathEdmonds–Karp: fewest-edge path

“Shortest” Means Edge Count

BFS does not maximize the bottleneck, minimize capacity, or minimize a monetary cost. Every positive residual edge counts as one step, regardless of whether its residual capacity is 1 or one billion.

Working Principle

Initialize the residual graph with the original capacities and zero-capacity reverse edges.
Run BFS from $s$, traversing only edges whose residual capacity is positive.
If BFS cannot reach $t$, stop: the current flow is maximum.
Use the BFS parent map to reconstruct a shortest residual path from $s$ to $t$.
Compute its bottleneck $\Delta$.
Subtract $\Delta$ from each forward residual edge, add $\Delta$ to its reverse edge, and increase the flow value.
Discard the old BFS labels and repeat on the updated residual graph.

The labels must be recomputed after every augmentation because residual edges can disappear or appear. What survives across rounds is not a particular BFS tree, but a monotonicity property of the shortest distances.

Reading the BFS Layers

BFS explores the residual graph in layers: distance 0, then 1, then 2, and so on. The first time it discovers the sink, its parent chain contains the fewest possible residual edges.

The path through B and C can carry much more per augmentation, but it is one edge longer. Edmonds–Karp chooses the two-edge path first; its guarantee comes from distance structure, not from greedily maximizing each push.

Worked Example

Use capacities $S\to A=3$, $S\to B=2$, $A\to T=2$, $B\to T=3$, and $A\to B=1$. Assume BFS considers A before B when both are discovered in the same layer.

The sink distance stays at 2, then rises to 3, then becomes infinite when the sink is unreachable. It does not have to increase after every augmentation; it only has to never decrease.

What tie-breaking changes

If several shortest residual paths exist, BFS may return any of them. Neighbor order can change the exact augmentation trace, but not the $O(VE^2)$ guarantee or the final maximum value.

Why BFS Bounds the Iteration Count

Max-flow correctness still comes from Ford–Fulkerson: if no residual $s$–$t$ path exists, the vertices reachable from $s$ define a cut whose capacity equals the current feasible flow. BFS is needed for the runtime guarantee.

Lemma 1: residual distances never decrease

Let $d_f(v)$ be the fewest residual edges from $s$ to $v$ before an augmentation. New residual edges can appear only as reverses of edges just used on a shortest path. If $u\to v$ was on that path, then $d_f(v)=d_f(u)+1$; the new reverse $v\to u$ points from a later layer to an earlier one. It cannot create a shortcut from $s$. After the update, every reachable vertex therefore has the same or a larger BFS distance.

Lemma 2: one directed edge can be critical only $O(V)$ times

Every augmentation saturates at least one edge on its shortest path; call it critical. Before the same directed edge $u\to v$ can become critical again, some later path must use the reverse direction and restore its residual capacity. The BFS-layer relationships then force $d_f(u)$ to increase by at least 2. Distances are at most $V-1$, so each directed edge can be critical only $O(V)$ times.

There are $O(E)$ residual edge directions. Charging every augmentation to one saturated critical edge gives at most $O(VE)$ augmentations.

Complexity Analysis

With adjacency lists, one BFS scans $O(V+E)=O(E)$ work on the usual connected flow-network representation. Path reconstruction and residual updates take $O(V)$, which is covered by that bound. Combining it with at most $O(VE)$ augmentations gives:

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

Property	Ford–Fulkerson with arbitrary paths	Edmonds–Karp
Path choice	Unspecified	BFS fewest-edge path
Integer-capacity bound	$O(EF)$	$O(VE^2)$
Depends on capacity magnitudes?	Yes	No
Irrational capacities	Arbitrary choices may not terminate	Terminates within the augmentation bound

The guarantee is strongly polynomial: the number of arithmetic operations depends on $V$ and $E$, not on the numeric sizes of the capacities.

Implementation

These versions accept nonnegative integer capacities, build a private residual graph, and aggregate repeated directed edges where the input format permits them. Each returns an augmentation trace plus the source side of a minimum cut. That extra information turns the code into a teaching and debugging tool.

State	Meaning	Invariant
`residual[u][v]`	Additional net flow allowed from $u$ to $v$	Traversed only when positive
`parent[v]`	Vertex that first discovered $v$ in the current BFS	Its chain has the fewest residual edges
`delta`	Minimum residual capacity on the chosen path	At least one path edge is saturated
`source_side`	Vertices reachable after the final unsuccessful BFS	Defines a minimum cut

from collections import defaultdict, deque

def edmonds_karp(capacity, source, sink):
    """Return (max-flow value, min-cut source side, augmentation trace)."""
    if source == sink:
        raise ValueError("source and sink must be different")

    residual = defaultdict(int)
    adjacency = defaultdict(list)

    def link(u, v):
        if v not in adjacency[u]:
            adjacency[u].append(v)

    for (u, v), cap in capacity.items():
        if not isinstance(cap, int) or cap < 0:
            raise ValueError("capacities must be nonnegative integers")
        residual[(u, v)] += cap
        residual[(v, u)] += 0
        link(u, v)
        link(v, u)  # a reverse residual edge may become positive later

    adjacency[source]
    adjacency[sink]

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

    value = 0
    augmentations = []
    while (parent := bfs_path()) is not None:
        path = []
        v = sink
        while v is not None:
            path.append(v)
            v = parent[v]
        path.reverse()

        delta = min(residual[(u, v)] for u, v in zip(path, path[1:]))
        for u, v in zip(path, path[1:]):
            residual[(u, v)] -= delta
            residual[(v, u)] += delta
        value += delta
        augmentations.append((path, delta))

    source_side = {source}
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in adjacency[u]:
            if residual[(u, v)] > 0 and v not in source_side:
                source_side.add(v)
                queue.append(v)

    return value, source_side, augmentations

capacity = {
    ("S", "A"): 3, ("S", "B"): 2, ("A", "T"): 2,
    ("B", "T"): 3, ("A", "B"): 1,
}
value, source_side, trace = edmonds_karp(capacity, "S", "T")
for path, delta in trace:
    print(" -> ".join(path), "push", delta)
print("Max flow:", value, "Cut source side:", sorted(source_side))

#include <algorithm>
#include <climits>
#include <iostream>
#include <queue>
#include <stdexcept>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

using Capacity = long long;
using Edge = tuple<string, string, Capacity>;
using Matrix = unordered_map<string, unordered_map<string, Capacity>>;

struct Augmentation { vector<string> path; Capacity delta; };
struct Result {
    Capacity value;
    unordered_set<string> sourceSide;
    vector<Augmentation> trace;
};

Result edmondsKarp(const vector<Edge>& edges,
                   const string& source, const string& sink) {
    if (source == sink) throw invalid_argument("source and sink must differ");

    Matrix residual;
    unordered_map<string, vector<string>> adjacency;
    auto link = [&](const string& u, const string& v) {
        auto& neighbors = adjacency[u];
        if (find(neighbors.begin(), neighbors.end(), v) == neighbors.end())
            neighbors.push_back(v);
    };
    for (const auto& [u, v, capacity] : edges) {
        if (capacity < 0) throw invalid_argument("negative capacity");
        residual[u][v] += capacity;
        residual[v][u] += 0;
        link(u, v);
        link(v, u);
    }
    adjacency[source];
    adjacency[sink];

    Capacity value = 0;
    vector<Augmentation> trace;
    while (true) {
        unordered_map<string, string> parent{{source, source}};
        queue<string> q;
        q.push(source);

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

        vector<string> path;
        for (string v = sink;; v = parent.at(v)) {
            path.push_back(v);
            if (v == source) break;
        }
        reverse(path.begin(), path.end());

        Capacity delta = LLONG_MAX;
        for (size_t i = 0; i + 1 < path.size(); ++i)
            delta = min(delta, residual[path[i]][path[i + 1]]);
        for (size_t i = 0; i + 1 < path.size(); ++i) {
            const string& u = path[i];
            const string& v = path[i + 1];
            residual[u][v] -= delta;
            residual[v][u] += delta;
        }
        value += delta;
        trace.push_back({path, delta});
    }

    unordered_set<string> sourceSide{source};
    queue<string> q;
    q.push(source);
    while (!q.empty()) {
        string u = q.front();
        q.pop();
        for (const string& v : adjacency[u]) {
            if (residual[u][v] > 0 && !sourceSide.count(v)) {
                sourceSide.insert(v);
                q.push(v);
            }
        }
    }
    return {value, sourceSide, trace};
}

int main() {
    vector<Edge> edges = {
        {"S", "A", 3}, {"S", "B", 2}, {"A", "T", 2},
        {"B", "T", 3}, {"A", "B", 1}
    };
    Result result = edmondsKarp(edges, "S", "T");
    for (const auto& step : result.trace) {
        for (size_t i = 0; i < step.path.size(); ++i)
            cout << (i ? " -> " : "") << step.path[i];
        cout << " push " << step.delta << '\n';
    }
    cout << "Max flow: " << result.value << '\n';
}

import java.util.*;

class EdmondsKarp {
    record Edge(String from, String to, long capacity) {}
    record Augmentation(List<String> path, long delta) {}
    record Result(long value, Set<String> sourceSide,
                  List<Augmentation> trace) {}

    static Result maxFlow(List<Edge> edges, String source, String sink) {
        if (source.equals(sink))
            throw new IllegalArgumentException("source and sink must differ");

        Map<String, Map<String, Long>> residual = new LinkedHashMap<>();
        Map<String, Set<String>> adjacency = new LinkedHashMap<>();
        for (Edge edge : edges) {
            if (edge.capacity() < 0)
                throw new IllegalArgumentException("negative capacity");
            residual.computeIfAbsent(edge.from(), k -> new LinkedHashMap<>())
                    .merge(edge.to(), edge.capacity(), Long::sum);
            residual.computeIfAbsent(edge.to(), k -> new LinkedHashMap<>())
                    .putIfAbsent(edge.from(), 0L);
            adjacency.computeIfAbsent(edge.from(), k -> new LinkedHashSet<>())
                    .add(edge.to());
            adjacency.computeIfAbsent(edge.to(), k -> new LinkedHashSet<>())
                    .add(edge.from());
        }
        adjacency.computeIfAbsent(source, k -> new LinkedHashSet<>());
        adjacency.computeIfAbsent(sink, k -> new LinkedHashSet<>());

        long value = 0;
        List<Augmentation> trace = new ArrayList<>();
        while (true) {
            Map<String, String> parent = new HashMap<>();
            parent.put(source, source);
            Deque<String> queue = new ArrayDeque<>();
            queue.add(source);

            while (!queue.isEmpty() && !parent.containsKey(sink)) {
                String u = queue.remove();
                for (String v : adjacency.getOrDefault(u, Set.of())) {
                    long spare = residual.getOrDefault(u, Map.of()).getOrDefault(v, 0L);
                    if (spare > 0 && !parent.containsKey(v)) {
                        parent.put(v, u);
                        queue.add(v);
                        if (v.equals(sink)) break;
                    }
                }
            }
            if (!parent.containsKey(sink)) break;

            List<String> path = new ArrayList<>();
            for (String v = sink;; v = parent.get(v)) {
                path.add(v);
                if (v.equals(source)) break;
            }
            Collections.reverse(path);

            long delta = Long.MAX_VALUE;
            for (int i = 0; i + 1 < path.size(); i++)
                delta = Math.min(delta, residual.get(path.get(i)).get(path.get(i + 1)));
            for (int i = 0; i + 1 < path.size(); i++) {
                String u = path.get(i), v = path.get(i + 1);
                residual.get(u).merge(v, -delta, Long::sum);
                residual.get(v).merge(u, delta, Long::sum);
            }
            value += delta;
            trace.add(new Augmentation(List.copyOf(path), delta));
        }

        Set<String> sourceSide = new LinkedHashSet<>();
        Deque<String> queue = new ArrayDeque<>();
        sourceSide.add(source);
        queue.add(source);
        while (!queue.isEmpty()) {
            String u = queue.remove();
            for (String v : adjacency.getOrDefault(u, Set.of())) {
                long spare = residual.getOrDefault(u, Map.of()).getOrDefault(v, 0L);
                if (spare > 0 && sourceSide.add(v)) queue.add(v);
            }
        }
        return new Result(value, sourceSide, trace);
    }

    public static void main(String[] args) {
        List<Edge> edges = List.of(
            new Edge("S", "A", 3), new Edge("S", "B", 2),
            new Edge("A", "T", 2), new Edge("B", "T", 3),
            new Edge("A", "B", 1)
        );
        Result result = maxFlow(edges, "S", "T");
        for (Augmentation step : result.trace())
            System.out.println(String.join(" -> ", step.path())
                               + " push " + step.delta());
        System.out.println("Max flow: " + result.value());
    }
}

Real-World Applications

Edmonds–Karp solves the same max-flow models as other maximum-flow algorithms. Its particular strengths are simple code, deterministic layer-based reasoning, and a capacity-independent guarantee—valuable when clarity and auditability matter more than leading performance.

Throughput

Network bottleneck analysis

Model routers or facilities as vertices and link limits as capacities. The maximum value measures throughput; the final residual reachability exposes a minimum cut.

Matching

Bipartite assignment

Unit-capacity edges turn an integral maximum flow into a matching. The augmenting trace makes each reassignment visible through reverse edges.

Connectivity

Edge-disjoint paths

Set every edge capacity to 1. The maximum flow value equals the largest number of edge-disjoint source-to-sink routes.

Verification

Reference implementations

Because the algorithm is compact and predictable, it is useful as a correctness oracle for testing more sophisticated max-flow code on small and medium instances.

Model boundaries

Basic max flow treats the transferred units as interchangeable and optimizes only quantity. Costs require minimum-cost flow; lower bounds require a circulation reduction; multiple commodities sharing edges form a harder model. A polynomial algorithm does not repair a mismatched model.

Choosing a Flow Algorithm

Method	Core rule	General bound	Use it when
Ford–Fulkerson	Any augmenting path	$O(EF)$ for integer capacities	The instance is small and integral, or the method itself is the lesson
Edmonds–Karp	One BFS path per augmentation	$O(VE^2)$	You want straightforward code and predictable behavior
Dinic	One BFS level graph, then a blocking flow	$O(V^2E)$	The network is larger and sparse
Push–relabel	Move local excess instead of finding full paths	$O(V^3)$ for a basic version	Dense or high-performance workloads justify more machinery

FROM EDMONDS–KARP TO DINIC Edmonds–Karp builds a BFS layer graph and uses one path from it. Dinic reuses that same layer graph to push along many compatible paths before running BFS again. The next speedup comes from amortizing the expensive global search.

Pitfalls & Debugging

Symptom	Likely cause	Fix
A path is not actually shortest	A stack, priority queue, or weighted distance replaced the FIFO queue	Use a true FIFO queue and mark a vertex when it is first enqueued
The answer is too small	Reverse residual edges are missing from adjacency	Add both directions to adjacency even when reverse capacity starts at 0
A later BFS uses stale information	Parent or visited state was reused after an augmentation	Create a fresh BFS parent map for every residual graph
The loop fails for $s=t$	The empty path has no finite bottleneck	Reject or explicitly define this input before searching
Results overflow	Capacities or the total exceed the numeric type	Use a suitably wide type and validate the expected range
The trace differs but the value matches	Several shortest paths exist and neighbor order changed	Use ordered adjacency for reproducibility; different valid ties are not an error

Rebuild BFS State Every Round

Residual capacities change after every push. An edge may vanish, and a reverse edge may appear. Reusing the previous parent tree can produce a non-residual path and destroys both correctness and the shortest-path guarantee.

Exercises

Build the Intuition in Layers

Trace: Re-run the worked example with B visited before A. Record which shortest path changes and which quantities do not.
Distinguish: Construct a graph where the fewest-edge augmenting path has a smaller bottleneck than a longer path.
Prove: Fill in the contradiction showing why a new reverse residual edge cannot decrease a BFS distance.
Measure: Instrument BFS edge scans, augmentation count, path length, and bottleneck. Compare against DFS Ford–Fulkerson on adversarial path orders.
Certify: For random graphs, compute the capacity of the returned source-side cut and assert that it equals the reported flow value.
Extend: Preserve one BFS level graph and find more than one compatible path before rebuilding it—the first conceptual step toward Dinic.

A compact mental model

Edmonds–Karp is disciplined Ford–Fulkerson. Residual edges keep choices reversible; BFS organizes those choices into layers; the bottleneck update improves the feasible flow; and the fact that layer distances never retreat limits how often the same edges can cause work.

Cookie Consent

Edmonds-Karp Algorithm

Contents

A Bit of History

From Ford–Fulkerson to Edmonds–Karp

Residual capacities

Push the bottleneck

Choose with BFS

“Shortest” Means Edge Count

Working Principle

Reading the BFS Layers

Worked Example

What tie-breaking changes

Why BFS Bounds the Iteration Count

Lemma 1: residual distances never decrease

Lemma 2: one directed edge can be critical only $O(V)$ times

Complexity Analysis

Implementation

Real-World Applications

Network bottleneck analysis

Bipartite assignment

Edge-disjoint paths

Reference implementations

Model boundaries

Choosing a Flow Algorithm

Pitfalls & Debugging

Rebuild BFS State Every Round

Exercises

Build the Intuition in Layers

A compact mental model

Cookie Consent

Edmonds-Karp Algorithm

Contents

A Bit of History

From Ford–Fulkerson to Edmonds–Karp

Residual capacities

Push the bottleneck

Choose with BFS

“Shortest” Means Edge Count

Working Principle

Reading the BFS Layers

Worked Example

What tie-breaking changes

Why BFS Bounds the Iteration Count

Lemma 1: residual distances never decrease

Lemma 2: one directed edge can be critical only $O(V)$ times

Complexity Analysis

Implementation

Real-World Applications

Network bottleneck analysis

Bipartite assignment

Edge-disjoint paths

Reference implementations

Model boundaries

Choosing a Flow Algorithm

Pitfalls & Debugging

Rebuild BFS State Every Round

Exercises

Build the Intuition in Layers

A compact mental model

Related Deep Dives

Graph Theory Series

Ford-Fulkerson Method

Hopcroft-Karp Algorithm