AdvancedO(V · E²)· Level 07

Max Flow (Edmonds-Karp)

Maximum flow from source to sink via BFS augmenting paths.

Intuition

Picture water flowing through pipes of varying capacity. Edmonds-Karp finds an unblocked path from source to sink (using BFS), pushes as much flow as the bottleneck allows, and repeats. The clever part: a 'reverse' edge lets us undo flow if a better routing appears later.

Step-by-step

1
Build a residual graph initialised to capacities.
2
Run BFS from source `s` to sink `t` in the residual graph.
3
If no path exists, stop — current flow is maximum.
4
Otherwise, push `bottleneck` units along the path, subtract from forward edges, add to reverse edges.
5
Repeat from step 2.

Pseudocode

pseudocode

EDMONDS_KARP(G, s, t):
  flow = 0
  while BFS finds path s -> t in residual:
    push min capacity along path
    update residual capacities
    flow += pushed
  return flow

Implementation (Python)

python

from collections import defaultdict, deque

def edmonds_karp(capacity, s, t):
    flow = 0
    cap = defaultdict(lambda: defaultdict(int))
    for u in capacity:
        for v, c in capacity[u].items():
            cap[u][v] = c

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

        # find bottleneck
        path_flow, v = float('inf'), t
        while parent[v] is not None:
            path_flow = min(path_flow, cap[parent[v]][v])
            v = parent[v]

        # augment
        v = t
        while parent[v] is not None:
            u = parent[v]
            cap[u][v] -= path_flow
            cap[v][u] += path_flow
            v = u
        flow += path_flow

Real-world applications

Bipartite matching
Network reliability and routing
Image segmentation (min-cut)
Project selection problems