Maximum Flow — Ford-Fulkerson and Edmonds-Karp Algorithm

Maximum flow is one of the most widely applicable algorithmic primitives in combinatorial optimisation. Bipartite matching reduces to max flow. Project selection with dependencies reduces to max flow. Image segmentation reduces to max flow. Network routing capacity planning reduces to max flow. If you see a problem involving 'maximum amount of something flowing through a constrained network', max flow is almost certainly the right tool.

Ford-Fulkerson (1956) established the foundational framework. Edmonds-Karp (1972) added the key insight: always augment along the shortest path (BFS) rather than any path. This single change moves the complexity from 'possibly exponential' to 'provably polynomial O(VE^2)' — and that guaranteed polynomiality is what makes the algorithm deployable in real systems.

Key Concepts

Flow network: Directed graph G=(V,E) with capacity c(u,v) ≥ 0 for each edge. Flow: f(u,v) satisfying: (1) capacity constraint: f(u,v) ≤ c(u,v), (2) flow conservation: inflow = outflow at all nodes except s and t. Residual graph: For each edge (u,v) with capacity c and flow f, add forward edge with residual c-f and backward edge with capacity f. Augmenting path: Any path from s to t in the residual graph. Max-flow min-cut theorem: Maximum flow = minimum cut capacity.

Ford-Fulkerson / Edmonds-Karp

Edmonds-Karp uses BFS to find shortest augmenting paths — guaranteeing O(VE²).

from collections import deque

def edmonds_karp(graph: dict, source: str, sink: str) -> int:
    """
    graph: {node: {neighbour: capacity}}
    Returns maximum flow from source to sink.
    """
    # Build residual graph
    residual = {u: dict(v_cap) for u, v_cap in graph.items()}
    for u in graph:
        for v in graph[u]:
            if v not in residual: residual[v] = {}
            if u not in residual[v]: residual[v][u] = 0

    def bfs_augmenting_path():
        visited = {source: None}
        queue = deque([source])
        while queue:
            node = queue.popleft()
            if node == sink: break
            for neighbour, cap in residual[node].items():
                if neighbour not in visited and cap > 0:
                    visited[neighbour] = node
                    queue.append(neighbour)
        if sink not in visited: return None, 0
        # Reconstruct path and find bottleneck
        path, node = [], sink
        while node != source:
            prev = visited[node]
            path.append((prev, node))
            node = prev
        bottleneck = min(residual[u][v] for u,v in path)
        return path, bottleneck

    max_flow = 0
    while True:
        path, bottleneck = bfs_augmenting_path()
        if path is None: break
        max_flow += bottleneck
        for u, v in path:
            residual[u][v] -= bottleneck
            residual[v][u] += bottleneck
    return max_flow

graph = {
    's': {'a': 10, 'b': 10},
    'a': {'t': 10, 'b': 2},
    'b': {'t': 10, 'a': 0},
    't': {}
}
print(edmonds_karp(graph, 's', 't'))  # 20

The Max-Flow Min-Cut Theorem

The maximum flow equals the capacity of the minimum cut (minimum total capacity of edges crossing from the source side to the sink side of any partition of V into S and T).

This duality is fundamental: finding max flow finds min cut, enabling applications like: - Network reliability: Minimum edges to remove to disconnect source from sink - Bipartite matching: Max matching = max flow (König's theorem) - Project selection: Which projects to take given dependencies

Complexity

Ford-Fulkerson with DFS: O(Ef) where f = max flow value — can be exponential Edmonds-Karp (BFS): O(VE²) — polynomial always Dinic's algorithm: O(V²E) — faster in practice

For most interview purposes, Edmonds-Karp is the expected answer.

Frequently Asked Questions