Ford–Fulkerson algorithm
The Ford–Fulkerson algorithm is a greedy algorithm for computing the maximum flow in a flow network, which is a directed graph consisting of vertices, edges with nonnegative capacities, a designated source vertex s, and a designated sink vertex t.[1] Introduced by Lester R. Ford Jr. and Delbert R. Fulkerson in 1956, the algorithm initializes the flow to zero and iteratively identifies an s-t augmenting path in the residual graph—a representation of the network that accounts for current flow and remaining capacities—and augments the flow along this path by the minimum residual capacity on it, repeating until no augmenting path exists.[2] This process guarantees convergence to a maximum flow, as established by the max-flow min-cut theorem, which proves that the value of the maximum flow equals the capacity of the minimum cut separating the source from the sink.[3] The algorithm's foundational role in network flow theory stems from its ability to solve not only the maximum flow problem but also related optimization challenges, such as the minimum cut and transportation problems, by leveraging the residual graph to "undo" suboptimal flow assignments through backward edges.[2] If all edge capacities are integers, the algorithm produces an integer-valued maximum flow, ensuring exact solutions without fractional values.[3] While the general time complexity depends on the choice of augmenting paths and can be exponential in the worst case (e.g., O(|E| \cdot v(f^)) where |E| is the number of edges and v(f^) is the maximum flow value), specific implementations like Edmonds-Karp (using breadth-first search for shortest paths) achieve polynomial time, O(|V| \cdot |E|^2), where |V| is the number of vertices.[3] Since its inception, the Ford–Fulkerson method has influenced numerous variants and applications in operations research, computer science, and engineering, including bipartite matching, image segmentation, and airline scheduling.[1]Introduction and Background
History and Development
The Ford–Fulkerson algorithm emerged from collaborative efforts at the RAND Corporation in the early 1950s, where mathematicians Lester Randolph Ford Jr. and Delbert Ray Fulkerson addressed network flow problems motivated by transportation and logistics challenges, particularly the evaluation of rail network capacities for military interdiction strategies. These efforts built on earlier work, including a secret RAND report by T.E. Harris and Gen. F.S. Ross in October 1955, which modeled rail net capacities inspired by analyses of Soviet railway systems. Ford and Fulkerson formalized their approach in a December 1955 RAND memorandum, laying the groundwork for systematic computation of maximum flows in networks. In their landmark 1956 paper, Ford and Fulkerson introduced the algorithm—now bearing their names—and established the max-flow min-cut theorem, demonstrating that the maximum flow value in a network equals the minimum capacity of a cut separating the source from the sink. Published in the Canadian Journal of Mathematics, the work titled "Maximal Flow Through a Network" provided both a constructive procedure for finding maximal flows and a duality result that unified flow conservation with cut capacities. The algorithm's development intersected with contemporaneous advances in linear programming, notably George Dantzig's simplex method, which Ford, Fulkerson, and Dantzig adapted for transportation problems in the mid-1950s, enabling efficient solutions to capacitated flow networks.[4] By the late 1950s, the Ford–Fulkerson framework influenced operations research by providing tools for optimizing resource allocation in complex systems and spurred graph theory developments, such as integral flow properties in bipartite matching. Ford and Fulkerson later consolidated their contributions in the 1962 monograph Flows in Networks, which formalized the theory and extended its applications.Problem Statement and Key Definitions
The maximum flow problem seeks to determine the greatest possible rate at which material, or flow, can be sent from a source vertex to a sink vertex in a capacitated network without violating edge capacity limits or flow conservation rules.[2] This problem models real-world scenarios such as transportation logistics, where the goal is to maximize throughput under resource constraints.[2] A flow network is formally defined as a directed graph G = (V, E), where V is the finite set of vertices and E \subseteq V \times V is the set of directed edges. The graph includes a source vertex s \in V and a sink vertex t \in V, with s \neq t. Each edge e \in E is assigned a nonnegative real-valued capacity c(e) \geq 0, which specifies the maximum amount of flow that can pass through that edge. A flow in the network is a function f: E \to \mathbb{R} that satisfies two key properties: (i) the capacity constraint, ensuring $0 \leq f(e) \leq c(e) for all e \in E; and (ii) the conservation of flow, requiring that for every vertex v \in V \setminus \{s, t\}, the total incoming flow equals the total outgoing flow, i.e., \sum_{\substack{e \in E \\ e \text{ enters } v}} f(e) = \sum_{\substack{e \in E \\ e \text{ leaves } v}} f(e). [2] The value of a flow f, denoted |f|, represents the net amount of flow leaving the source (or equivalently, entering the sink) and is given by |f| = \sum_{\substack{e \in E \\ e \text{ leaves } s}} f(e) = \sum_{\substack{e \in E \\ e \text{ enters } t}} f(e). [2] The maximum flow problem is then to compute a flow f of maximum value |f| among all feasible flows in the network.[2] Given a flow f in G, the residual graph G_f = (V, E_f) captures the remaining capacity for potential flow adjustments. It has the same vertex set V as G, but its edge set E_f consists of residual edges: for each original edge e = (u, v) \in E, a forward residual edge (u, v) exists in E_f if f(e) < c(e), with residual capacity c_f(e) = c(e) - f(e); additionally, a backward residual edge (v, u) exists in E_f if f(e) > 0, with residual capacity c_f(e) = f(e). These backward edges allow for flow reduction along paths to enable increases elsewhere.[2] A cut in the flow network is a partition of the vertex set V into two subsets S and T = V \setminus S such that s \in S and t \in T. The capacity of the cut (S, T), denoted c(S, T), is the sum of the capacities of all edges directed from S to T, i.e., c(S, T) = \sum_{\substack{e = (u, v) \in E \\ u \in S, v \in T}} c(e). [2] This measure quantifies the minimum capacity that must be "severed" to disconnect the source from the sink.[2]Algorithm Mechanics
Core Procedure
The Ford–Fulkerson algorithm computes the maximum flow in a capacitated network by iteratively augmenting an initial zero flow along paths from the source to the sink in the residual graph until no such path remains.[2] The procedure begins with initialization of the flow function f to zero for all edges, ensuring that the initial flow satisfies the capacity constraints and conservation properties of a valid flow.[2] In each iteration, the algorithm searches for a directed path p from the source s to the sink t in the current residual graph G_f, where residual capacities c_f(e) represent the remaining allowable flow on each edge e. If such a path exists, it computes the bottleneck capacity b = \min_{e \in p} c_f(e), which is the maximum amount of additional flow that can be pushed along p without violating capacities. The flow is then augmented by adding b to f(e) for each forward edge e in p and subtracting b from f(e) for the corresponding backward edges (initially zero), thereby updating the residual graph: forward residual capacities decrease by b, while backward residual capacities increase by b to allow potential flow reductions in future iterations.[2][5] The following pseudocode outlines the core procedure:[5] (adapted from the original method in Ford and Fulkerson, 1956)[2] The algorithm terminates when no path from s to t exists in G_f, at which point the flow f is maximum, as guaranteed by the max-flow min-cut theorem: the value of the flow equals the capacity of the minimum cut separating s from t, and no greater flow is possible.[2] This theorem underpins the correctness of the procedure, ensuring that repeated augmentation reaches the optimum.[2]FordFulkerson(G, c, s, t): Initialize f(e) = 0 for all [edges](/page/Edge) e in G while there exists a path p from s to t in the residual graph G_f: b = min_{e in p} c_f(e) // [bottleneck](/page/Bottleneck) [capacity](/page/Capacity) for each [edge](/page/Edge) e in p: augment f along e by b // f(e) += b for forward, -= b for backward update residual capacities in G_f return fFordFulkerson(G, c, s, t): Initialize f(e) = 0 for all [edges](/page/Edge) e in G while there exists a path p from s to t in the residual graph G_f: b = min_{e in p} c_f(e) // [bottleneck](/page/Bottleneck) [capacity](/page/Capacity) for each [edge](/page/Edge) e in p: augment f along e by b // f(e) += b for forward, -= b for backward update residual capacities in G_f return f
Augmenting Paths and Residual Graphs
The residual graph G_f associated with a flow network G = (V, E) and a feasible flow f is a directed graph with the same vertex set V as G, and an edge from u to v if and only if the residual capacity c_f(u, v) > 0, where c_f(u, v) = c(u, v) - f(u, v) for forward edges and c_f(u, v) = f(v, u) for backward edges corresponding to existing flow.[6] This construction, introduced in the foundational work on maximum flows, enables the representation of both unused capacity and the potential to redirect existing flow.[1] An augmenting path in the context of the Ford–Fulkerson algorithm is defined as a simple path p from the source s to the sink t in the residual graph G_f such that the residual capacity c_f(e) > 0 for every edge e along p.[6] Such paths exist as long as the current flow is not maximal, allowing incremental improvements to the flow value.[1] Given an augmenting path p, the bottleneck capacity b(p) is computed as the minimum residual capacity along the path: b(p) = \min_{e \in p} c_f(e). This value determines the maximum amount of additional flow that can be pushed along p without violating capacity constraints.[6] To augment the flow, the algorithm updates the flow function f by adding b(p) to the flow on each forward edge e = (u, v) in p (i.e., f(e) \leftarrow f(e) + b(p)) and subtracting b(p) from the flow on each backward edge \hat{e} = (v, u) in p if such flow exists (i.e., f(\hat{e}) \leftarrow f(\hat{e}) - b(p)); initially, with no prior flow on backward edges, only forward augmentations occur.[6] This step increases the net flow from s to t by exactly b(p).[1] Following augmentation, the residual capacities are updated to reflect the changes: for each forward edge e in p, c_f(e) \leftarrow c_f(e) - b(p), reducing available forward capacity; for the corresponding backward edge \hat{e}, c_f(\hat{e}) \leftarrow c_f(\hat{e}) + b(p), which introduces or increases capacity in the reverse direction.[6] These backward edges in the residual graph permit "undoing" portions of previously sent flow, enabling rerouting to find new augmenting paths that might otherwise be blocked, thus allowing the algorithm to explore alternative flow configurations for achieving maximality.[1]Theoretical Properties
Correctness Proof
The max-flow min-cut theorem states that in any flow network, the value of the maximum flow equals the capacity of the minimum s-t cut.[7] This theorem establishes the optimality condition for flows and cuts, providing the foundation for proving the correctness of the Ford–Fulkerson algorithm. To prove the theorem and the algorithm's correctness, first note the weak duality: for any feasible flow f and any s-t cut (S, T), the flow value |f| is at most the cut capacity c(S, T).[7] This follows because the net flow across the cut cannot exceed its total capacity, as the flow out of S equals the flow into T by conservation, and backward edges in the cut do not contribute positively to the net outflow. Lemma 1: For any feasible flow f, |f| \leq c(S, T) holds for every s-t cut (S, T).This lemma captures the weak duality, ensuring no flow exceeds any cut capacity.[7] The Ford–Fulkerson algorithm starts with a zero flow and repeatedly augments along paths in the residual graph G_f until no augmenting path from s to t exists. Upon termination, the final flow f is feasible by construction, as each augmentation preserves feasibility.[8] Lemma 2: If there is no augmenting path in G_f, then |f| = c(S, T) for the s-t cut (S, T) where S is the set of vertices reachable from s in G_f and T = V \setminus S.
To see this, the absence of an augmenting path implies no residual path crosses from S to T. Thus, for every edge u \to v with u \in S and v \in T, f(u, v) = c(u, v) (forward edges are saturated), and f(v, u) = 0 (no backward residual capacity). The net flow across the cut equals c(S, T), so |f| = c(S, T).[8] Combining the lemmas yields strong duality at termination: since |f| \leq \min c(S, T) by Lemma 1 and |f| = c(S, T) for some cut by Lemma 2, f achieves the minimum cut capacity and is thus maximum. This cut is minimal, confirming the algorithm computes the maximum flow.[7]
Time Complexity Analysis
The time complexity of the Ford–Fulkerson algorithm depends critically on the input capacities and the method used to select augmenting paths. In the general case, assuming integer capacities, the algorithm performs at most |f_{\max}| augmenting steps, where |f_{\max}| denotes the value of the maximum flow, because each augmentation increases the flow by at least 1 unit. Each such step requires finding an augmenting path in the residual graph, which takes O(|E|) time using methods like depth-first search, and updating the residual capacities along the path also takes O(|E|) time. Thus, the overall time complexity is O(|E| \cdot |f_{\max}|).[9] This bound highlights the pseudo-polynomial nature of the algorithm, as the running time scales linearly with the maximum flow value, which can be exponentially large in the input size if capacities are encoded in binary. Arbitrary selection of augmenting paths can exacerbate this by favoring paths with small bottleneck capacities, leading to numerous augmentations and performance that degrades with larger capacity values. For instance, repeatedly choosing paths that augment by only 1 unit can force up to |f_{\max}| iterations even when larger augmentations are possible.[9] When capacities are not integers, particularly if they are irrational or non-commensurable, the algorithm may fail to terminate, as the sequence of augmentations can converge to a non-maximum flow value without reaching it exactly, resulting in an infinite loop of ever-smaller flow increases. In practice, implementations assume rational capacities represented with finite precision to avoid this issue, ensuring termination under bounded arithmetic.[9] To achieve polynomial-time performance independent of capacity values, variants of the Ford–Fulkerson algorithm employ structured path selection, such as using breadth-first search to find shortest augmenting paths, which bounds the number of augmentations by O(|V| \cdot |E|).[9]Illustrative Examples
Integer Capacity Network Example
To illustrate the Ford–Fulkerson algorithm's convergence on a network with integer capacities, consider a directed graph with four vertices: source s, intermediate vertices a and b, and sink t. The edges and their integer capacities are as follows: s \to a with capacity 4, s \to b with capacity 2, a \to b with capacity 2, a \to t with capacity 3, and b \to t with capacity 3.[10] The algorithm begins with zero flow on all edges and iteratively finds augmenting paths in the residual graph until no such path exists. In the first iteration, an augmenting path s \to a \to t is found, with bottleneck capacity \min(4, 3) = 3. Augmenting the flow by 3 along this path updates the residuals: forward residual on s \to a becomes 1, on a \to t becomes 0; backward residuals a \to s and t \to a become 3 each. The current flow value is 3.[10] In the second iteration, the path s \to b \to t has bottleneck \min(2, 3) = 2. Augmenting by 2 updates residuals: forward on s \to b becomes 0, on b \to t becomes 1; backward b \to s and t \to b become 2 each. The flow value is now 5. The residual capacities after this step are shown in the table below (backward edges with positive residual are included where flow has been sent).| Edge | Residual Capacity (Forward) | Residual Capacity (Backward) |
|---|---|---|
| s \to a | 1 | 3 |
| s \to b | 0 | 2 |
| a \to b | 2 | 0 |
| a \to t | 0 | 3 |
| b \to t | 1 | 2 |
Non-Terminating Behavior Example
A well-known example demonstrating the non-terminating behavior of the Ford–Fulkerson algorithm occurs when edge capacities include irrational numbers and augmenting paths are selected in a manner that produces an infinite sequence of progressively smaller flow augmentations. Consider a flow network with vertices s (source), t (sink), and intermediate vertices u, v, w, x. The edges include s \to u with capacity C (large, e.g., 100), s \to w with capacity C, u \to v with capacity r, u \to w with capacity C, w \to v with capacity 1, w \to x with capacity 1, v \to t with capacity C, and x \to t with capacity C, where r = \frac{\sqrt{5} - 1}{2} \approx 0.618 (satisfying r^2 = 1 - r).[13] In this setup, if the algorithm selects suboptimal paths, it begins by augmenting along the path s \to w \to v \to t, with bottleneck capacity 1, increasing the flow by 1 and updating the residual graph by reducing forward capacities and adding backward edges (e.g., residual v \to w = 1). Subsequent iterations proceed with paths such as s \to u \to v \to w \to x \to t with bottleneck r (using the backward v \to w), then s \to w \to v \to u \to t with bottleneck r, followed by another s \to u \to v \to w \to x \to t with bottleneck r^2, and s \to x \to w \to v \to t with bottleneck r^2. This pattern repeats, with pairs of augmentations at levels r^k for k = 1, 2, 3, \dots, where each r^k < 1 and decreases geometrically. The residual graph updates introduce smaller positive residual capacities due to the irrational r, ensuring an augmenting path always exists.[13] The total flow after infinitely many such paired augmentations approaches $1 + 2 \sum_{k=1}^{\infty} r^k = 1 + \frac{2r}{1 - r} = 2 + \sqrt{5} \approx 4.236, which is much less than the maximum flow of approximately $2C = 200. Because r is irrational, the residual capacities never exactly cancel to zero in finite steps, leading to an infinite loop despite the flow converging asymptotically to a suboptimal value. This illustrates that while the algorithm preserves the max-flow min-cut theorem's correctness (no augmenting path implies maximality), termination is not guaranteed without integer capacities or systematic path selection.[13] To avoid non-termination, the algorithm should use integer capacities, where each augmentation increases flow by at least 1, bounding iterations by the max-flow value, or employ a systematic path search like breadth-first search (as in the Edmonds-Karp variant) to ensure polynomial time. The key lesson is that Ford–Fulkerson relies on careful implementation to guarantee finite termination, even though it always computes a valid flow when it halts.[13]Variants and Implementations
Edmonds-Karp Breadth-First Variant
The Edmonds–Karp algorithm represents a breadth-first search (BFS) variant of the Ford–Fulkerson method, where augmenting paths are selected as the shortest paths in the residual graph measured by the number of edges. This approach systematically explores the residual network level by level, starting from the source vertex, to identify the minimal-length augmenting path available at each iteration.[9] Introduced by Jack Edmonds and Richard M. Karp in their 1972 paper on network flow efficiency, this variant refines the original Ford–Fulkerson framework by enforcing a structured path selection mechanism that promotes rapid convergence.[9] The algorithm proceeds by repeatedly applying BFS to trace a path from source to sink in the residual graph, augmenting the flow along this path by its bottleneck capacity, and updating the residual capacities until no such path exists.[9] A key distinction from the general Ford–Fulkerson algorithm lies in its guaranteed polynomial-time performance, independent of the specific capacity values, which can lead to non-polynomial behavior in the unrestricted case due to potentially numerous or inefficient augmentations.[14] By prioritizing shortest paths via BFS, the Edmonds–Karp method maintains a layered graph structure in the residual network, where vertices are grouped by their distance from the source; this layering prevents the selection of circuitous paths that could prolong execution.[14] The BFS strategy bounds the total number of augmentations to O(|V| |E|), as the length of the shortest augmenting path (in edge count) is non-decreasing across iterations and can increase at most O(|V|) times, forming distinct phases; within each phase, at most O(|E|) augmentations occur before the path length advances, since each residual edge can become critical (bottleneck) only a bounded number of times per phase.[14] Each BFS traversal requires O(|E|) time using standard adjacency-list representations, yielding an overall time complexity of O(|V| |E|^2).[14] This polynomial bound addresses the general Ford–Fulkerson's potential for exponential augmentations under arbitrary path choices, as noted in broader complexity analyses.[14]Practical Implementation Considerations
Implementing the Ford–Fulkerson algorithm requires careful selection of data structures to efficiently manage the flow network and residual capacities. Typically, the graph is represented using adjacency lists to store edges, allowing for O(1) access to neighbors of a vertex, which is essential for path-finding operations. Capacities and flows are maintained in a 2D array or a map associated with each edge pair (u, v) and its reverse (v, u), ensuring that forward and backward edges in the residual graph are handled symmetrically; this structure supports quick updates during augmentation without rebuilding the graph.[15] Path-finding in the residual graph can use either depth-first search (DFS) or breadth-first search (BFS), each with trade-offs in simplicity and performance. Recursive DFS is straightforward to implement for finding augmenting paths and suits small to medium graphs due to its stack-based exploration, but it risks stack overflow in large graphs with deep recursion; an iterative version using an explicit stack mitigates this. BFS, as in the Edmonds-Karp variant, guarantees shorter paths and polynomial time but requires a queue and parent array, increasing space slightly while providing better worst-case efficiency for dense networks.[16] For the Edmonds-Karp implementation, which uses BFS for path selection, the following Python-like pseudocode illustrates the core functions. The BFS function employs a queue to explore levels from the source and a parent array to reconstruct paths, marking visited nodes to avoid cycles.This code assumes the input graph is an n x n capacity matrix, with graph representing the capacity from u to v; zero capacities are implicitly handled by skipping edges with no residual flow.[16][15] For large networks where the basic algorithm may be slow, capacity scaling techniques preprocess edges by scaling capacities to powers of 2 and solving in phases, reducing iterations, while Dinic's algorithm layers the graph with BFS and uses DFS within levels for faster blocking flows. These alternatives are often preferred in practice for graphs with thousands of vertices.[15] Edge cases must be addressed to ensure robustness. Zero-capacity edges are naturally ignored in residual graph traversals, as they contribute no flow. Disconnected graphs, where no path exists from source to sink, terminate the algorithm immediately with zero flow upon failed path-finding. For networks with multiple sources or sinks, reductions introduce a super-source connected to all sources with infinite capacity and a super-sink connected from all sinks similarly, transforming the problem without altering the maximum flow.[15] Numerical stability is a key concern, particularly with floating-point capacities, which can lead to precision errors in residual updates and path flows; implementations should prefer integer capacities when possible, as the algorithm guarantees integer maximum flows under the integral flow theorem, avoiding accumulation of rounding errors over iterations. If floats are necessary, high-precision arithmetic or epsilon comparisons for zero residuals help maintain accuracy.[15]pythonfrom collections import deque def bfs(graph, source, sink, parent, residual): visited = [False] * len(graph) queue = deque() queue.append(source) visited[source] = True parent[source] = -1 while queue: u = queue.popleft() for v in range(len([graph](/page/Graph))): if not visited[v] and [residual](/page/Residual)[u][v] > 0: queue.append(v) parent[v] = u visited[v] = True if v == [sink](/page/Sink): return True return False def edmonds_karp([graph](/page/Graph), [source](/page/Source), [sink](/page/Sink)): n = len([graph](/page/Graph)) parent = [-1] * n max_flow = 0 [residual](/page/Residual) = [row[:] for row in [graph](/page/Graph)] # Copy capacities as initial residual while bfs([graph](/page/Graph), [source](/page/Source), [sink](/page/Sink), parent, [residual](/page/Residual)): path_flow = float('inf') s = [sink](/page/Sink) while s != [source](/page/Source): path_flow = min(path_flow, [residual](/page/Residual)[parent[s]][s]) s = parent[s] max_flow += path_flow v = sink while v != source: u = parent[v] residual[u][v] -= path_flow residual[v][u] += path_flow # Update backward edge v = u return max_flowfrom collections import deque def bfs(graph, source, sink, parent, residual): visited = [False] * len(graph) queue = deque() queue.append(source) visited[source] = True parent[source] = -1 while queue: u = queue.popleft() for v in range(len([graph](/page/Graph))): if not visited[v] and [residual](/page/Residual)[u][v] > 0: queue.append(v) parent[v] = u visited[v] = True if v == [sink](/page/Sink): return True return False def edmonds_karp([graph](/page/Graph), [source](/page/Source), [sink](/page/Sink)): n = len([graph](/page/Graph)) parent = [-1] * n max_flow = 0 [residual](/page/Residual) = [row[:] for row in [graph](/page/Graph)] # Copy capacities as initial residual while bfs([graph](/page/Graph), [source](/page/Source), [sink](/page/Sink), parent, [residual](/page/Residual)): path_flow = float('inf') s = [sink](/page/Sink) while s != [source](/page/Source): path_flow = min(path_flow, [residual](/page/Residual)[parent[s]][s]) s = parent[s] max_flow += path_flow v = sink while v != source: u = parent[v] residual[u][v] -= path_flow residual[v][u] += path_flow # Update backward edge v = u return max_flow