Max-Flow: Ford-Fulkerson and Edmonds-Karp

The Maximum Flow Problem

Given a directed graph G = (V, E) with a capacity function c: E → ℝ≥0, a source node s and a sink node t, find the maximum amount of flow that can be routed from s to t.

Real-world motivations:

Network bandwidth allocation
Traffic routing (road/packet networks)
Supply chain optimization
Hospital-patient matching
Image segmentation (computer vision)

Formal Definitions

A flow f: E → ℝ≥0 satisfies:

Capacity constraint: f(u, v) ≤ c(u, v) for all edges (u, v)
Flow conservation: For all v ≠ s, t: Σ f(u, v) = Σ f(v, w) (in-flow = out-flow)

The value of flow |f| = net flow out of s = Σ f(s, v).

The residual graph Gf has:

A forward edge (u, v) with capacity c(u, v) − f(u, v) when f(u, v) < c(u, v)
A backward edge (v, u) with capacity f(u, v) when f(u, v) > 0

An augmenting path is any s-t path in Gf.

Ford-Fulkerson Algorithm

python

from collections import deque

def ford_fulkerson_bfs(capacity, source, sink):
    """
    Edmonds-Karp: Ford-Fulkerson with BFS augmenting path.
    
    Args:
        capacity: n x n capacity matrix
        source:   source node index
        sink:     sink node index
    Returns:
        (max_flow, residual_graph)
    
    Time:  O(V * E^2) — Edmonds-Karp guarantee
    Space: O(V^2)
    """
    n = len(capacity)
    # Residual graph starts as copy of capacity
    residual = [row[:] for row in capacity]
    max_flow = 0
    
    while True:
        # BFS: find shortest augmenting path
        parent = [-1] * n
        parent[source] = source
        queue = deque([source])
        
        while queue and parent[sink] == -1:
            u = queue.popleft()
            for v in range(n):
                if parent[v] == -1 and residual[u][v] > 0:
                    parent[v] = u
                    queue.append(v)
        
        if parent[sink] == -1:
            break  # No more augmenting paths
        
        # Trace path and find bottleneck capacity
        path_flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            path_flow = min(path_flow, residual[u][v])
            v = u
        
        # Augment along the path
        max_flow += path_flow
        v = sink
        while v != source:
            u = parent[v]
            residual[u][v] -= path_flow  # Reduce forward capacity
            residual[v][u] += path_flow  # Increase backward capacity
            v = u
    
    return max_flow, residual


# Example usage:
# 0 → 1 (cap 10), 0 → 2 (cap 10), 1 → 3 (cap 10), 2 → 3 (cap 10), 1 → 2 (cap 1)
cap = [
    [0, 10, 10,  0],
    [0,  0,  1, 10],
    [0,  0,  0, 10],
    [0,  0,  0,  0],
]
flow, residual = ford_fulkerson_bfs(cap, source=0, sink=3)
print(f"Max flow: {flow}")  # 20

Why BFS Guarantees O(VE²)?

Without BFS (e.g., using DFS), Ford-Fulkerson can take O(E · max_flow) iterations — potentially infinite for irrational capacities. With BFS (Edmonds-Karp):

Each augmentation increases the shortest-path distance of some edge
Each edge can "saturate and reappear" at most O(V) times
Total augmentations: O(V · E)
Each BFS: O(V + E)
Total: O(V · E²)

Handling Bidirectional Edges

Many real graphs have edges in both directions. To handle correctly:

python

def build_residual_with_adj(n, edges):
    """
    Build residual graph for edges (u, v, capacity).
    Uses adjacency list + edge list for O(E) space.
    """
    # Each edge i stores its reverse at index i^1
    graph = [[] for _ in range(n)]
    cap = []
    
    def add_edge(u, v, c):
        graph[u].append(len(cap))
        cap.append(c)
        graph[v].append(len(cap))
        cap.append(0)  # Reverse edge starts with 0 capacity
    
    for u, v, c in edges:
        add_edge(u, v, c)
    
    return graph, cap

Practice Problems

Find the maximum flow from s to t in a given network (LeetCode 1557 / classic)
Multiple sources/sinks: add a super-source S connected to all sources, super-sink T connected from all sinks
Flow with lower bounds: transform l(e) ≤ f(e) ≤ c(e) to standard max-flow
Verify the max-flow min-cut theorem on the example above

ADVANCED ALGORITHMS - NETWORK FLOW:Max-Flow: Ford-Fulkerson and Edmonds-Karp