Ford–Fulkerson algorithm
Greedy algorithm for maximum flow in a network.
The Ford–Fulkerson method, often called the Ford–Fulkerson algorithm (FFA), is a greedy procedure used to find the maximum flow in a flow network. It is sometimes labeled a "method" rather than a strict "algorithm" because the way it finds augmenting paths in the residual graph is left unspecified, so different implementations can have different running times. The approach was introduced in 1956 by L. R. Ford Jr. and D. R. Fulkerson. The name "Ford–Fulkerson" is also commonly applied to the Edmonds–Karp algorithm, which is a fully defined version of the method.
The core idea is straightforward: as long as there exists a path from the source to the sink where every edge still has available capacity, flow is sent along that path. This process repeats, finding another such path each time. A path with remaining capacity is called an augmenting path.
In the algorithm, we start with a graph \(G(V, E)\), where each edge from \(u\) to \(v\) has a capacity \(c(u, v)\) and a flow \(f(u, v)\). The goal is to maximize the flow from source \(s\) to sink \(t\). After each step, the flow in the network remains valid. The residual network \(G_f(V, E_f)\) is defined with capacities \(c_f(u, v) = c(u, v) - f(u, v)\) and no flow. Notably, the residual network may allow flow from \(v\) to \(u\) even if the original network does not: if \(f(u, v) > 0\) and \(c(v, u) = 0\), then \(c_f(v, u) = c(v, u) - f(v, u) = f(u, v) > 0\).
The path in step 2 can be found using methods like breadth-first search (BFS) or depth-first search on the residual network. Using BFS is known as the Edmonds–Karp algorithm. When no more augmenting paths can be found, the source \(s\) cannot reach the sink \(t\) in the residual network. If \(S\) is the set of nodes reachable from \(s\) in that residual network, then the total capacity of edges from \(S\) to the rest of \(V\) in the original network equals the total flow from \(s\) to \(t\) and also serves as an upper bound for all such flows. This demonstrates that the flow found is maximal (see the Max-flow Min-cut theorem).
If the graph has multiple sources and sinks, the problem is handled by adding a new super-source \(s^*\) with an edge to each original source \(s \in S\), where the capacity is \(c(s^*, s) = d_s = \sum_{(s,u) \in E} c(s, u)\). Similarly, a new super-sink \(t^*\) is added with an edge from each original sink \(t \in T\) to \(t^*\).
- field
- Computer science, operations research
- known_for
- Maximum flow problem, Ford–Fulkerson algorithm
- type
- Algorithm
Lore & Background
The Ford–Fulkerson algorithm, published in 1956 by L. R. Ford Jr. and D. R. Fulkerson, is a greedy method for computing the maximum flow in a flow network. It is often termed a "method" rather than a fully specified algorithm because the procedure for finding augmenting paths in the residual graph is left undefined, leading to multiple implementations with different running times. The algorithm maintains a legal flow at every step, operating on a residual network where each edge’s capacity is the original capacity minus the current flow; this residual network may permit flow along edges not present in the original graph. The process iterates: as long as a path from source to sink exists in the residual network with available capacity on every edge—called an augmenting path—flow is sent along that path, and the residual network is updated. When no such path remains, the flow is maximal, a fact proven by the max-flow min-cut theorem: the set of nodes reachable from the source in the residual network defines a cut whose total capacity equals the flow found. The algorithm can handle multiple sources and sinks by adding a super-source and super-sink, and nodes with capacity constraints are split into two nodes connected by an edge of that capacity. If capacities are integers, the runtime is bounded by O(E * |f|), where E is the number of edges and |f| is the maximum flow value, because each augmenting path is found in O(E) time and increases flow by at least 1. However, with irrational capacities, the algorithm may not terminate, and the flow may not converge to the maximum; a non-terminating example exists using specific edge capacities and an infinite sequence of augmenting paths. The fully specified Edmonds–Karp algorithm, which uses breadth-first search to find augmenting paths, guarantees termination in O(V * E²) time regardless of flow values.
Reader's Guide
The Ford–Fulkerson algorithm is foundational in network flow theory, underpinning many practical applications such as transportation, telecommunications, and bipartite matching. Its significance lies in its simplicity and the proof of optimality via the max-flow min-cut theorem. However, the algorithm's runtime is not guaranteed to terminate with irrational flow values; with integer capacities, the runtime is bounded by O(Ef), where E is the number of edges and f is the maximum flow. The Edmonds–Karp algorithm, a specific implementation using breadth-first search, is often also called Ford–Fulkerson. The method can be extended to handle multiple sources and sinks by adding a super-source and super-sink, and node capacity constraints by splitting nodes.
Did You Know?
- The Ford–Fulkerson method is sometimes called a 'method' rather than an 'algorithm' because the way to find augmenting paths is not fully specified.
- The name 'Ford–Fulkerson' is often also used for the Edmonds–Karp algorithm, which uses breadth-first search.
- When capacities are integers, the runtime of Ford–Fulkerson is bounded by O(Ef), where E is the number of edges and f is the maximum flow.
- The algorithm may not terminate if flow values are irrational.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record