Edmonds-Karp Algorithm

Ford-Fulkerson with breadth-first shortest augmenting paths, giving a capacity-independent polynomial bound.

The refinement

Edmonds-Karp is the Ford-Fulkerson method with one rule: always augment along the augmenting path with the fewest edges, found by breadth-first search in the residual graph. This choice removes the dependence on capacity magnitudes and bounds the number of augmentations by O(V * E).

Why the bound holds

Kronos motion — materials first

Using BFS, the shortest-path distance from the source to any node never decreases across augmentations. Each augmentation saturates at least one edge, and any given edge can become the saturating bottleneck at most O(V) times before its endpoints move farther from the source. Multiplying gives O(V * E) augmentations, each costing O(E) for the BFS, so the total is O(V * E^2).

Implementation

python

from collections import deque

def bfs_augment(cap, s, t):
    parent = {s: None}
    q = deque([s])
    while q:
        u = q.popleft()
        for v in cap[u]:
            if v not in parent and cap[u][v] > 0:
                parent[v] = u
                if v == t:
                    return parent
                q.append(v)
    return None

Practical notes

Simple to implement correctly; a reasonable default when E is modest.
Slower than Dinic on dense graphs and on unit-capacity bipartite matching.
Handles multiple sources or sinks by adding a super-source and super-sink.
Integer capacities keep all intermediate flows integral, which many applications rely on.

Relationship to other methods

Edmonds-Karp and Dinic both use BFS layering, but Dinic augments many shortest paths per phase via blocking flows, cutting the worst case to O(V^2 * E). For bipartite matching Dinic reduces further to O(E * sqrt(V)).