Ford-Fulkerson Algorithm
Also known as: Ford-Fulkerson method, augmenting path method
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.
Key highlights
- 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
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
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.
Strengths & limitations
- 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
- 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
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
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.
Sources
- 1.Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.
- 2.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.ISBN 978-0-262-03384-8
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Ford-Fulkerson Algorithm. ScholarGate. https://scholargate.app/operations-research/ford-fulkerson-algorithm