Ford-Fulkerson Algorithm: Maximum Flow

Key Insights

Ford-Fulkerson finds maximum flow by repeatedly discovering augmenting paths and pushing flow until no path from source to sink exists in the residual graph
The algorithm’s termination and efficiency depend entirely on path selection strategy—use BFS (Edmonds-Karp) to guarantee O(VE²) polynomial time complexity
Maximum flow equals minimum cut, making this algorithm applicable to problems ranging from bipartite matching to image segmentation and network reliability analysis

Introduction to Network Flow

Network flow problems model how resources move through systems with limited capacity. Think of water pipes, internet bandwidth, highway traffic, or supply chain logistics. Each connection has a maximum throughput, and we want to push as much “stuff” from point A to point B as possible.

A flow network is a directed graph where each edge has a capacity—the maximum flow it can carry. Two special nodes exist: the source (where flow originates) and the sink (where flow terminates). The maximum flow problem asks: what’s the greatest amount of flow we can push from source to sink while respecting capacity constraints?

This isn’t just academic. Maximum flow solves bipartite matching (assigning jobs to workers), network reliability analysis (finding bottlenecks), image segmentation (separating foreground from background), and resource allocation problems across industries.

Key Concepts and Terminology

Before diving into code, you need to understand four concepts:

Capacity constraints: Flow through an edge cannot exceed its capacity. If a pipe handles 10 units, you can’t push 15 through it.

Flow conservation: Except for source and sink, flow into a node equals flow out. Nothing gets created or destroyed mid-network.

Residual graph: After pushing flow through an edge, we track remaining capacity. If an edge has capacity 10 and carries 6 units of flow, the residual capacity is 4. Critically, we also add a “reverse edge” with capacity equal to the current flow—this allows the algorithm to “undo” previous decisions.

Augmenting path: Any path from source to sink in the residual graph where every edge has positive residual capacity. Finding these paths is the core of Ford-Fulkerson.

Here’s how to represent a flow network:

class FlowNetwork:
    def __init__(self, vertices: int):
        self.V = vertices
        # Adjacency list: vertex -> [(neighbor, capacity), ...]
        self.graph = [[] for _ in range(vertices)]
        # Capacity matrix for O(1) lookups
        self.capacity = [[0] * vertices for _ in range(vertices)]
    
    def add_edge(self, u: int, v: int, cap: int):
        # Add forward edge with capacity
        self.capacity[u][v] = cap
        # Track adjacency (add reverse edge for residual graph)
        self.graph[u].append(v)
        self.graph[v].append(u)  # Reverse edge for residual

I use both adjacency lists (for efficient neighbor iteration) and a capacity matrix (for O(1) capacity lookups). This hybrid approach balances memory and speed for typical problem sizes.

The Ford-Fulkerson Method

The algorithm is elegantly simple:

Start with zero flow everywhere
Find any augmenting path from source to sink in the residual graph
Determine the bottleneck—the minimum residual capacity along the path
Push that much flow along the path (update residual capacities)
Repeat until no augmenting path exists

The total flow pushed equals the maximum flow.

Here’s the core implementation using DFS for path finding:

def ford_fulkerson_dfs(capacity: list, source: int, sink: int) -> int:
    n = len(capacity)
    # Create residual capacity matrix (copy of original)
    residual = [row[:] for row in capacity]
    
    def dfs(node: int, sink: int, visited: set, min_cap: int) -> int:
        if node == sink:
            return min_cap
        
        visited.add(node)
        for neighbor in range(n):
            if neighbor not in visited and residual[node][neighbor] > 0:
                # Bottleneck is minimum capacity along path
                new_cap = min(min_cap, residual[node][neighbor])
                result = dfs(neighbor, sink, visited, new_cap)
                
                if result > 0:
                    # Update residual graph
                    residual[node][neighbor] -= result
                    residual[neighbor][node] += result  # Reverse edge
                    return result
        
        return 0
    
    max_flow = 0
    while True:
        # Find augmenting path via DFS
        flow = dfs(source, sink, set(), float('inf'))
        if flow == 0:
            break
        max_flow += flow
    
    return max_flow

The reverse edge update (residual[neighbor][node] += result) is crucial. It allows the algorithm to “change its mind” about previous flow assignments when a better overall solution exists.

Edmonds-Karp Optimization

Plain Ford-Fulkerson has a problem: with arbitrary path selection, it might not terminate for irrational capacities, and even with integers, it can take O(E × max_flow) iterations. If your maximum flow is 1,000,000, that’s potentially millions of iterations.

Edmonds-Karp fixes this by always choosing the shortest augmenting path (fewest edges) using BFS. This guarantees O(VE²) time complexity regardless of capacity values.

from collections import deque

def bfs_find_path(residual: list, source: int, sink: int) -> list:
    """Find shortest augmenting path using BFS. Returns parent array."""
    n = len(residual)
    parent = [-1] * n
    visited = [False] * n
    
    queue = deque([source])
    visited[source] = True
    
    while queue:
        node = queue.popleft()
        
        for neighbor in range(n):
            if not visited[neighbor] and residual[node][neighbor] > 0:
                visited[neighbor] = True
                parent[neighbor] = node
                
                if neighbor == sink:
                    return parent  # Found path to sink
                
                queue.append(neighbor)
    
    return None  # No path exists

BFS explores nodes level by level, guaranteeing the first path found is shortest. This bounds the number of augmenting path searches to O(VE), and each BFS takes O(E), giving us O(VE²) overall.

Complete Implementation Walkthrough

Here’s a production-ready max-flow solver:

from collections import deque
from typing import Optional, Tuple

class MaxFlowSolver:
    def __init__(self, vertices: int):
        self.V = vertices
        self.capacity = [[0] * vertices for _ in range(vertices)]
        self.flow = [[0] * vertices for _ in range(vertices)]
    
    def add_edge(self, u: int, v: int, cap: int):
        self.capacity[u][v] += cap  # += handles parallel edges
    
    def bfs(self, source: int, sink: int, parent: list) -> bool:
        visited = [False] * self.V
        queue = deque([source])
        visited[source] = True
        
        while queue:
            u = queue.popleft()
            
            for v in range(self.V):
                residual = self.capacity[u][v] - self.flow[u][v]
                if not visited[v] and residual > 0:
                    visited[v] = True
                    parent[v] = u
                    if v == sink:
                        return True
                    queue.append(v)
        
        return False
    
    def max_flow(self, source: int, sink: int) -> int:
        parent = [-1] * self.V
        total_flow = 0
        
        while self.bfs(source, sink, parent):
            # Find bottleneck capacity
            path_flow = float('inf')
            v = sink
            while v != source:
                u = parent[v]
                residual = self.capacity[u][v] - self.flow[u][v]
                path_flow = min(path_flow, residual)
                v = u
            
            # Update flow along path
            v = sink
            while v != source:
                u = parent[v]
                self.flow[u][v] += path_flow
                self.flow[v][u] -= path_flow  # Reverse flow
                v = u
            
            total_flow += path_flow
            parent = [-1] * self.V  # Reset for next BFS
        
        return total_flow

# Example usage
solver = MaxFlowSolver(6)
# Build sample network: 0=source, 5=sink
edges = [(0,1,16), (0,2,13), (1,2,10), (1,3,12), 
         (2,1,4), (2,4,14), (3,2,9), (3,5,20), (4,3,7), (4,5,4)]
for u, v, cap in edges:
    solver.add_edge(u, v, cap)

print(f"Maximum flow: {solver.max_flow(0, 5)}")  # Output: 23

Practical Applications

Bipartite Matching

Maximum bipartite matching reduces directly to max-flow. Create a super-source connected to all nodes on the left, a super-sink connected to all nodes on the right, and set all capacities to 1.

def max_bipartite_matching(left_nodes: int, right_nodes: int, 
                           edges: list) -> int:
    """
    Find maximum matching in bipartite graph.
    edges: list of (left_idx, right_idx) pairs
    """
    # Node layout: 0=source, 1..left=left nodes, 
    #              left+1..left+right=right nodes, last=sink
    total = 2 + left_nodes + right_nodes
    source, sink = 0, total - 1
    
    solver = MaxFlowSolver(total)
    
    # Source to all left nodes (capacity 1)
    for i in range(1, left_nodes + 1):
        solver.add_edge(source, i, 1)
    
    # All right nodes to sink (capacity 1)
    for j in range(left_nodes + 1, left_nodes + right_nodes + 1):
        solver.add_edge(j, sink, 1)
    
    # Edges between left and right (capacity 1)
    for left_idx, right_idx in edges:
        u = left_idx + 1  # Offset for source
        v = left_nodes + 1 + right_idx
        solver.add_edge(u, v, 1)
    
    return solver.max_flow(source, sink)

# Example: 3 workers, 3 jobs, some compatibility edges
edges = [(0,0), (0,1), (1,0), (1,2), (2,1), (2,2)]
print(f"Maximum matching: {max_bipartite_matching(3, 3, edges)}")  # Output: 3

This elegantly solves job assignment, course scheduling, and any problem requiring maximum one-to-one pairing.

Complexity Analysis and Alternatives

Ford-Fulkerson with DFS: O(E × max_flow) time. Acceptable for small capacities, dangerous for large ones.

Edmonds-Karp (BFS): O(VE²) time, O(V²) space for the capacity matrix. This is your go-to for most problems.

When to use alternatives:

Dinic’s algorithm: O(V²E) time. Significantly faster for dense graphs or unit-capacity networks where it runs in O(E√V).
Push-Relabel: O(V²E) or O(V³) depending on implementation. Often faster in practice for very large graphs due to better cache locality.

For competitive programming and typical software engineering problems, Edmonds-Karp handles graphs with thousands of nodes efficiently. Switch to Dinic’s when you’re dealing with tens of thousands of nodes or need guaranteed performance on worst-case inputs.

The max-flow min-cut theorem guarantees that maximum flow equals the capacity of the minimum cut—the smallest total capacity you’d need to remove to disconnect source from sink. This duality makes Ford-Fulkerson applicable far beyond its obvious use cases.