Loading learning content...
In 1956, Lester Ford Jr. and Delbert Fulkerson published a paper that would become one of the most influential works in combinatorial optimization. Their Ford-Fulkerson method provided not just an algorithm, but a way of thinking about flow problems that unified theory and practice.
The genius of Ford-Fulkerson lies in its elegant simplicity: repeatedly find a path with available capacity from source to sink, and push flow along it. The magic is in the details—specifically, in the concept of residual graphs that allow us to correct suboptimal choices made earlier.
By the end of this page, you'll understand the complete Ford-Fulkerson method: how it uses residual graphs and augmenting paths, why it's correct, when it terminates, its time complexity characteristics, and practical implementation considerations. You'll also learn about the Edmonds-Karp optimization that guarantees polynomial runtime.
The Ford-Fulkerson method is beautifully simple at its core:
Ford-Fulkerson Method:
1. Initialize flow f(u,v) = 0 for all edges
2. While there exists an augmenting path p from s to t in residual graph G_f:
a. Find the bottleneck capacity: c_f(p) = min{c_f(u,v) : (u,v) ∈ p}
b. Augment flow: For each edge (u,v) in p:
- If (u,v) is a forward edge: f(u,v) += c_f(p)
- If (u,v) is a backward edge: f(v,u) -= c_f(p)
3. Return the maximum flow f
Key Insight: The method doesn't specify how to find augmenting paths—it's a method, not an algorithm. Different path-finding strategies yield different algorithms with different performance characteristics.
| Term | Definition | Intuition |
|---|---|---|
| Augmenting path | Path from s to t in residual graph G_f | A route where we can push more flow |
| Bottleneck | Minimum residual capacity along the path | The limiting constraint for this path |
| Forward edge | Original edge with remaining capacity | We add flow in the intended direction |
| Backward edge | Represents flow that can be canceled | We 'undo' previous flow to reroute it |
| Residual capacity | c_f(u,v) = c(u,v) - f(u,v) or f(v,u) | What we can still push or cancel |
Ford-Fulkerson is a 'method' because it leaves the path-finding strategy unspecified. Using DFS to find paths is one option (original Ford-Fulkerson). Using BFS guarantees polynomial time (Edmonds-Karp). Using shortest path by weight gives another variant. The framework is constant; the path strategy varies.
Let's trace through Ford-Fulkerson on a concrete example. Consider this network:
[A]
↗ ↘
10 10
↗ ↘
[S] 10 [T]
↘ ↗↘ ↗
10 10
↘ ↗
[B]
With edges:
Initial State: All flows are 0.
Iteration 1:
After Iteration 1:
Residual graph:
[A]
↗ ↘
0 0 (forward edges saturated)
↙ ↙ (backward edges: 10 each)
[S] 10 [T]
↘ ↗↘ ↗
10 10 (still at full capacity)
↘ ↗
[B]
Iteration 2:
After Iteration 2:
No more augmenting paths exist from S to T. All edges leaving S are saturated.
Result: Maximum flow = 20
In this example, we didn't need backward edges. But consider if we had found S→A→B→T first (using the cross-edge A→B). Then we'd have used only part of A→T's capacity. The backward edge A←B in the residual graph would allow a subsequent path to 'reroute' that flow directly to T.
The backward edge concept can seem counterintuitive. Let's see a case where it's absolutely essential.
The Problem Network:
[A]
↗ ↘
3 2
↗ ↘
[S] 1 [T]
↘ ↓↑ ↗
3 2
↘ ↗
[B]
Edges: S→A (3), S→B (3), A→B (1), A→T (2), B→T (2)
Bad Path Choice (Iteration 1): S → A → B → T
Current Flow State:
Without backward edges, we could only find:
But the optimal is 5! We need backward edges.
Iteration 2 (with backward edges): S → B → A → T
Wait—there's no forward edge B→A! But in the residual graph, there's a backward edge B→A with capacity 1 (because f(A,B) = 1).
The backward edge let us 'cancel' the A→B flow and reroute it directly A→T. Simultaneously, we sent new flow S→B. The net effect: flow goes S→A→T AND S→B→T, achieving higher total flow than if we were stuck with our initial A→B commitment.
Completing the Example:
Iteration 3: S → A → T (residual capacity 2, 1) → bottleneck 1 → total flow 3
Iteration 4: S → B → T (residual capacity 2, 1) → bottleneck 1 → total flow 4
Iteration 5: S → A → T (residual capacity 1, 0—wait, A→T is saturated)
Actually, let's recalculate carefully after iteration 2:
Residual capacities:
Plus backward edges for non-zero flows.
Iterations 3-4: We can push 2 more through S→A→T and 1 more through S→B→T.
Final Maximum Flow: 5 (verified: S can output 3+3=6 but T can only receive 2+2+1 routed optimally = 4... let me recalculate)
Actually the max flow is min(total S outflow capacity, total T inflow capacity) = min(6, 4) = 4. The key point stands: backward edges enable flow values that forward-only approaches cannot achieve.
The correctness of Ford-Fulkerson rests on a beautiful theorem connecting maximum flows to minimum cuts. We'll explore this deeply on the next page, but here's the essence.
Key Theorem (Max-Flow Min-Cut):
The maximum value of a flow from s to t equals the minimum capacity of any s-t cut.
What's an s-t Cut?
A cut (S, T) partitions vertices into two sets:
The capacity of the cut is the sum of capacities of edges from S to T: $$c(S, T) = \sum_{u \in S, v \in T} c(u, v)$$
Why Max-Flow = Min-Cut Proves Correctness:
When Ford-Fulkerson terminates (no augmenting path exists):
The genius: we don't prove we found the best flow directly. We prove that when no augmenting path exists, we've hit the theoretical ceiling (the minimum cut). No flow can exceed the min cut, and we've achieved it.
Proof Sketch of Flow Conservation During Augmentation:
We need to verify that after each augmentation, the resulting f is still a valid flow:
Capacity constraints: We only push flow equal to the bottleneck, which by definition is ≤ the residual capacity of each edge. So we never exceed capacity.
Conservation: For any intermediate vertex v on the augmenting path:
For vertices not on the path: No flow changes, conservation trivially maintained.
Thus, each augmentation produces a valid flow with higher value by exactly the bottleneck amount.
The Termination Question:
Does Ford-Fulkerson always terminate? The answer depends on the capacities:
Integer Capacities: Yes, terminates. Each augmentation increases flow by at least 1. Maximum flow is bounded by sum of capacities out of s, which is finite. Maximum iterations = O(max_flow).
Rational Capacities: Yes, terminates. Can reduce to integers by multiplying by LCD.
Irrational Capacities: May NOT terminate! Ford and Fulkerson constructed pathological examples where the method oscillates forever with flow converging but never reaching the maximum.
Fortunately, the non-termination case is artificial. All real-world capacities are rational.
| Factor | Analysis | Implication |
|---|---|---|
| Path finding | O(E) with DFS/BFS | Each iteration is efficient |
| Number of iterations | O(max_flow) worst case | Can be huge if max flow is large |
| Total complexity | O(E × max_flow) | Pseudo-polynomial (depends on output size) |
| Practical issue | max_flow could be exponential in network size | Bad for large capacity values |
O(E × max_flow) is pseudo-polynomial—it depends on the numeric value of capacities, not just the network size. A network with 10 vertices and edges of capacity 1,000,000,000 could require a billion iterations! This motivated the search for truly polynomial algorithms.
A Worst-Case Example:
[A]
↗ ↘
1000 1000
↗ 1 ↘
[S] ↗ ↘ [T]
↘ 1 ↗
1000 1000
↘ ↗
[B]
With the A→B edge having capacity 1, and if we unluckily alternate paths:
This could take 2000 iterations instead of the optimal 2 (S→A→T and S→B→T).
The fix: choose augmenting paths wisely, which leads us to Edmonds-Karp.
The Edmonds-Karp algorithm is Ford-Fulkerson with one crucial specification: always use BFS to find augmenting paths. This simple choice transforms pseudo-polynomial into truly polynomial.
Key Insight:
BFS finds the shortest augmenting path (in terms of number of edges). This has a remarkable property:
Theorem (Edmonds-Karp Bound): The total number of augmentations is at most O(V × E).
Why? Two key observations:
After each augmentation, at least one edge becomes "critical" (saturated in forward direction or emptied in backward direction).
An edge can become critical at most O(V) times. Each time it becomes critical on a path of length d, the next time it's critical (if ever), the path length is ≥ d + 2.
Since path lengths are bounded by V and can only increase (or edge is permanently removed), each edge is critical at most O(V) times.
Total augmentations ≤ O(VE).
Edmonds-Karp runs in O(VE²) time. Each augmentation takes O(E) for BFS, and there are O(VE) augmentations. This is polynomial in the network size, independent of capacity values!
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
from collections import deque def edmonds_karp(graph, source, sink): """ Edmonds-Karp algorithm for maximum flow. Uses BFS to find shortest augmenting paths. Args: graph: Dict[node, Dict[neighbor, capacity]] source: Source vertex sink: Sink vertex Returns: Tuple of (max_flow_value, flow_dict) """ # Initialize flow to zero flow = {u: {v: 0 for v in graph.get(u, {})} for u in graph} def bfs_find_path(): """Find augmenting path using BFS, return path and bottleneck.""" parent = {source: None} visited = {source} queue = deque([source]) while queue: u = queue.popleft() for v in get_residual_neighbors(u): if v not in visited: visited.add(v) parent[v] = u if v == sink: # Reconstruct path and find bottleneck path = [] curr = sink while curr != source: prev = parent[curr] path.append((prev, curr)) curr = prev path.reverse() # Find bottleneck bottleneck = float('inf') for u, v in path: bottleneck = min(bottleneck, residual_capacity(u, v)) return path, bottleneck queue.append(v) return None, 0 # No augmenting path found def get_residual_neighbors(u): """Get neighbors with positive residual capacity.""" neighbors = [] # Forward edges for v, cap in graph.get(u, {}).items(): if cap - flow.get(u, {}).get(v, 0) > 0: neighbors.append(v) # Backward edges for v in graph: if u in graph.get(v, {}) and flow.get(v, {}).get(u, 0) > 0: neighbors.append(v) return neighbors def residual_capacity(u, v): """Get residual capacity from u to v.""" forward = graph.get(u, {}).get(v, 0) - flow.get(u, {}).get(v, 0) backward = flow.get(v, {}).get(u, 0) return max(forward, backward) max_flow = 0 while True: path, bottleneck = bfs_find_path() if path is None: break # Augment flow along path for u, v in path: if v in graph.get(u, {}): # Forward edge if u not in flow: flow[u] = {} flow[u][v] = flow.get(u, {}).get(v, 0) + bottleneck else: # Backward edge flow[v][u] = flow.get(v, {}).get(u, 0) - bottleneck max_flow += bottleneck return max_flow, flow # Example usagegraph = { 'S': {'A': 10, 'B': 10}, 'A': {'B': 2, 'T': 10}, 'B': {'T': 10}, 'T': {}} max_flow, flow = edmonds_karp(graph, 'S', 'T')print(f"Maximum flow: {max_flow}") # Output: 20Moving from pseudocode to working implementation requires attention to several practical details.
Instead of explicitly maintaining a separate residual graph, store capacity and flow together. The residual capacity of (u,v) is cap[u][v] - flow[u][v], and the backward residual is flow[u][v]. This halves memory usage and simplifies updates.
Performance Comparison:
| Implementation Choice | Time Impact | Space Impact | Code Complexity |
|---|---|---|---|
| Adjacency matrix | O(V²) BFS | O(V²) | Simple |
| Adjacency list | O(V+E) BFS | O(V+E) | Moderate |
| Explicit residual | Faster queries | 2× edge storage | More complex |
| Implicit residual | Slower queries | 1× edge storage | Simpler |
For competitive programming, adjacency matrix with implicit residual is often preferred for simplicity. For production code with large graphs, adjacency list with optimized data structures wins.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990
class MaxFlow: """ Optimized max flow implementation using adjacency list with implicit residual graph computation. """ def __init__(self, n): """Initialize with n vertices (0-indexed).""" self.n = n self.adj = [[] for _ in range(n)] # adj[u] = list of (v, cap, rev_idx) def add_edge(self, u, v, cap): """ Add directed edge u -> v with capacity cap. Automatically adds reverse edge with capacity 0. """ # Forward edge: (to, capacity, index of reverse edge) # Reverse edge: (to, capacity, index of forward edge) self.adj[u].append([v, cap, len(self.adj[v])]) self.adj[v].append([u, 0, len(self.adj[u]) - 1]) def bfs(self, source, sink): """Find shortest augmenting path, return parent array or None.""" parent = [-1] * self.n # (prev_node, edge_index) parent[source] = (source, -1) queue = deque([source]) while queue: u = queue.popleft() for i, (v, cap, _) in enumerate(self.adj[u]): if cap > 0 and parent[v] == -1: parent[v] = (u, i) if v == sink: return parent queue.append(v) return None def max_flow(self, source, sink): """Compute maximum flow from source to sink.""" total_flow = 0 while True: parent = self.bfs(source, sink) if parent is None: break # Find bottleneck bottleneck = float('inf') v = sink while v != source: u, i = parent[v] bottleneck = min(bottleneck, self.adj[u][i][1]) v = u # Augment flow v = sink while v != source: u, i = parent[v] self.adj[u][i][1] -= bottleneck # Decrease forward capacity rev_i = self.adj[u][i][2] self.adj[v][rev_i][1] += bottleneck # Increase backward capacity v = u total_flow += bottleneck return total_flow # Example: Maximum matching as max flow# 3 workers, 3 jobs, with compatibility edgesmf = MaxFlow(8) # Super-source=0, workers=1,2,3, jobs=4,5,6, super-sink=7 # Super-source to workers (capacity 1 each)mf.add_edge(0, 1, 1)mf.add_edge(0, 2, 1)mf.add_edge(0, 3, 1) # Worker-job compatibilitymf.add_edge(1, 4, 1) # Worker 1 can do job 4mf.add_edge(1, 5, 1) # Worker 1 can do job 5mf.add_edge(2, 5, 1) # Worker 2 can do job 5mf.add_edge(3, 5, 1) # Worker 3 can do job 5mf.add_edge(3, 6, 1) # Worker 3 can do job 6 # Jobs to super-sink (capacity 1 each)mf.add_edge(4, 7, 1)mf.add_edge(5, 7, 1)mf.add_edge(6, 7, 1) print(f"Maximum matching: {mf.max_flow(0, 7)}") # Output: 3Ford-Fulkerson and Edmonds-Karp are foundational, but more sophisticated algorithms exist for better performance in specific cases.
| Algorithm | Time Complexity | Key Technique | Best Use Case |
|---|---|---|---|
| Ford-Fulkerson (DFS) | O(E × max_flow) | Any augmenting path | Small capacities |
| Edmonds-Karp (BFS) | O(VE²) | Shortest path augmentation | General purpose |
| Dinic's Algorithm | O(V²E) | Blocking flows | Dense graphs |
| Push-Relabel | O(V²E) or O(V³) | Local operations | Very dense graphs |
| Dinic on unit capacity | O(E√V) | Special structure | Bipartite matching |
Dinic's Algorithm:
Dinic improves on Edmonds-Karp by finding ALL shortest paths of a given length before moving to longer paths. It constructs a "level graph" using BFS, then finds blocking flows using DFS. This achieves O(V²E) in general and O(E√V) on unit-capacity graphs.
Push-Relabel:
Instead of finding paths globally, push-relabel works locally: vertices have heights, and flow is "pushed" downhill. When no downhill neighbor exists, the vertex is "relabeled" (raised). This paradigm avoids the overhead of repeated BFS/DFS and excels on dense graphs.
Practical Considerations:
Start with Edmonds-Karp. If performance is insufficient, try Dinic. For bipartite matching or unit capacities, Dinic's O(E√V) is hard to beat. Push-relabel is most practical when you have a high-quality library implementation.
We've explored the Ford-Fulkerson method comprehensively. Let's consolidate the key insights:
What's Next:
We've mentioned the Max-Flow Min-Cut Theorem several times—it's time to explore it deeply. This beautiful duality between flows and cuts is one of the most important results in combinatorial optimization, with applications far beyond network flow. Understanding this theorem provides intuition for why flow algorithms work and enables recognizing new problems as flow problems.
You now understand the mechanics of finding maximum flow: the augmenting path framework, the role of residual graphs, correctness arguments, complexity analysis, and practical implementation. The Ford-Fulkerson method is your algorithmic workhorse for flow problems.