Ford-Fulkerson Algorithm
- Introduced by
- Lester R. Ford and Delbert R. Fulkerson
- Year
- 1956
- Type
- algorithm
- Family
- Graph Algorithms
What does it do?
The Ford-Fulkerson Algorithm, developed by Lester R. Ford and Delbert R. Fulkerson in 1956, is a foundational method for computing the maximum flow in a flow network.
It finds the maximum amount of flow that can be sent from a source to a sink through a directed graph with capacity constraints on edges.
The intuition behind the method
The algorithm works by repeatedly finding augmenting paths from source to sink through the residual network, where each edge has remaining capacity. Each path contributes an additional flow equal to its bottleneck capacity (the edge with minimum remaining capacity on the path). The process continues until no more augmenting paths exist, at which point the maximum flow is achieved. The key insight is the max-flow min-cut theorem: the maximum flow equals the minimum cut capacity in the network.
History
Ford and Fulkerson introduced the maximum flow problem and their seminal algorithm in 1956. The work was revolutionary, establishing both an algorithmic method and the celebrated max-flow min-cut theorem. Edmonds and Karp (1972) improved the worst-case complexity by using breadth-first search for path selection. Subsequent advances by Dinic, Karzanov, and others led to even faster algorithms, but the Ford-Fulkerson method remains a classic and pedagogically valuable algorithm in computer science.
When to use it
Apply the Ford-Fulkerson algorithm to find maximum flow in directed or undirected flow networks with positive integer capacities. It works well for small to medium-sized networks and provides intuitive understanding of network flow concepts. For very large networks or when integral flows are required, consider Edmonds-Karp (using BFS) or Dinic's algorithm for better worst-case performance. Use it when understanding algorithm behavior is as important as speed.
Limitations and considerations
- Time complexity depends on capacity values (not polynomial in general; can be exponential with irrational capacities)
- May not terminate if capacities are irrational (requires careful implementation with rational arithmetic)
- Less efficient than specialized algorithms like Edmonds-Karp or Dinic on large networks
- Sensitive to augmenting path selection order
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Simple and intuitive approach based on augmenting paths
- Optimal solution guaranteed when capacities are rational or integral
- Efficient for networks with small integer capacities
- Forms the theoretical foundation for understanding max-flow min-cut duality
- Works with both directed and undirected graphs
Applications
- Network routing: maximizing data throughput from source to destination in communication networks
- Transportation networks: determining maximum cargo capacity between cities considering road and rail constraints
- Bipartite matching: finding maximum matchings in bipartite graphs by constructing flow networks
- Image segmentation: using max-flow algorithms to partition images into foreground and background
- Airline scheduling: optimizing aircraft routing to maximize passenger flow through hub-and-spoke networks
- Protein analysis: computing maximum flow in biological networks for understanding interaction pathways
How it works
How it works
Initialize the residual graph with capacities equal to the original edge capacities and zero flow on all edges.
Find an augmenting path from source to sink in the residual graph using depth-first or breadth-first search, compute the minimum capacity along the path, and add this flow to all edges on the path while reducing their residual capacities.
Repeat augmentation until no augmenting path exists in the residual graph; the total accumulated flow is the maximum flow.
Common pitfalls
- Choosing poor augmenting paths that result in slow convergence or incorrect results
- Failing to properly update residual capacities or adding reverse edges for undoing flow
- Using integer division or floating-point arithmetic when exact arithmetic is required for correctness
Frequently asked questions
What is the max-flow min-cut theorem?
The theorem states that the maximum flow from source to sink equals the minimum capacity of any cut separating the source from the sink. This provides both a theoretical insight and a verification method for flow algorithms.
Why does the algorithm sometimes converge slowly?
With unfortunate path selections, the algorithm may augment by only one unit of flow per iteration, even when larger augmentations are possible. Using breadth-first search (Edmonds-Karp) ensures polynomial-time convergence.
How does the algorithm handle undirected edges?
Replace each undirected edge with two directed edges in opposite directions, both with the same capacity. The algorithm then finds flow on the directed network.
What is the difference between flow on an edge and residual capacity?
Flow on an edge represents the amount of material sent along it, while residual capacity is the remaining capacity available. Residual capacity decreases as flow increases, and reverse edges track the ability to undo flow.
Related methods
Sources
Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.
Open DOI referenceCopied.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN: 978-0-262-03384-8Copied.