Home/Graphs/Edmonds-Karp
Search algorithmsCTRL K

Edmonds-Karp

· maximum flow · shortest augmenting paths
/graphs/edmonds-karp
FLOW
0
source to sink so far
PATHS
0
augmenting paths used
BOTTLENECK
—
of the current path
LENGTH
—
edges in the current path
SATURATED
0
edges at full capacity
augmenting pathcarrying flowcut edgesource side of the cut
10 nodes · 15 edges · seed 7 · 7 steps
step 0 / 6
Nodes10
edmonds_karp.ts
1
function edmondsKarp(graph: Graph, source: Node, sink: Node) {
2
  const flow = new Map<Edge, number>(); let total = 0;
3
  while (true) {
4
    const parent = bfs(graph, flow, source, sink); // shortest augmenting path in the residual graph
5
    if (!parent.has(sink)) break;
6
    let bottleneck = Infinity;
7
    for (let node = sink; node !== source; node = parent.get(node)!.from) bottleneck = Math.min(bottleneck, residual(parent.get(node)!, flow));
8
    for (let node = sink; node !== source; node = parent.get(node)!.from) push(parent.get(node)!, bottleneck, flow);
9
    total += bottleneck;
10
  }
11
  return total;
12
}
CURRENT STEP
line 2

Source A, sink J. Every edge shows flow / capacity, all flows 0.

// how it works

Understanding Edmonds-Karp

Edmonds-Karp · push flow along the shortest path until none is left
01

The idea

A flow sends units from a source to a sink through edges with capacities. Ford and Fulkerson's method finds any path with spare capacity, pushes as much as its tightest edge allows, and repeats; when no such path is left the flow is maximum. Pushing flow also creates reverse residual capacity, so a later path can undo an earlier bad choice.

Edmonds-Karp fixes the one thing Ford-Fulkerson left open: which path to take. Choosing the shortest augmenting path, by BFS, bounds the number of augmentations by V · E regardless of the capacities. When the search from the source finally stalls, the reachable nodes form a minimum cut whose capacity equals the flow.

02

The four stages

1
residualspare capacity forward, flow backward
2
BFSthe shortest source-to-sink path with spare capacity
3
bottleneckthe smallest residual capacity on it
4
augmentpush that much along the path
03

Complexity

best
O(E)one path saturates the sink
average
O(V · E²)at most V · E augmentations of O(E) each
worst
O(V · E²)independent of the capacities
space
O(V + E)flows and the BFS parents
04

Versus its siblings

AUGMENTATIONS · 1 000 NODES, 5 000 EDGES
edmonds-karp
2,500
dinic
300
push-relabel
900
ford-fulkerson (dfs)
100,000
Ford-Fulkerson with DFS can take as many augmentations as the flow value
05

Pseudocode

EDMONDSKARP(graph, source, sink)
  flow ← 0 on every edge
  repeat
    BFS from source over edges with residual capacity (capacity − flow forward, flow backward)
    if the sink was not reached: stop, the flow is maximum
    bottleneck ← the smallest residual capacity on the path; add it along the path (subtract on backward edges)
06

When to use

Bipartite matching, project selection, image segmentation, scheduling with capacities: all reduce to max flow.
Minimum cuts: which edges to remove to disconnect two nodes, straight from the last residual search.
07

Pitfalls

Forgetting the reverse residual edges makes the algorithm wrong, not just slow.
Irrational capacities can make plain Ford-Fulkerson loop forever; BFS order avoids that.
For big graphs Dinic's level graphs or push-relabel are several times faster.
08

History

Ford and Fulkerson published the augmenting path method in 1956, for a RAND study of rail capacity between the Soviet Union and Eastern Europe. Yefim Dinitz in 1970 and Jack Edmonds with Richard Karp in 1972 showed that shortest augmenting paths make it polynomial; the max-flow min-cut theorem is from the same 1956 paper.

Back to Graphs