FordFulkersonin

Ford-Fulkerson method, also known as the Ford-Fulkerson algorithm, is a classic method for computing the maximum flow in a flow network. Given a directed graph with capacities on edges, a source s and a sink t, it repeatedly finds an augmenting path from s to t in the residual graph and increases the flow along that path by the minimum residual capacity on the path (the bottleneck). After each augmentation, residual capacities are updated, and backward edges may appear to allow undoing previous flow.

Developed by L. R. Ford Jr. and D. R. Fulkerson in 1956, the method is foundational to the theory of maximum flow problems. It provided a simple framework that could be specialized into various implementations.

Crucially, the process stops when no s-t path exists in the residual graph; at that point the current flow is maximum, and its value equals the capacity of a minimum s-t cut, per the max-flow min-cut theorem. If all capacities are integers, the algorithm produces an integer maximum flow.

Without a prescribed strategy for choosing augmenting paths, the algorithm can require arbitrarily many augmentations and may run in exponential time when capacities are not rational. A common variant is Edmonds-Karp, which always selects the shortest augmenting path using breadth-first search, yielding a time bound of O(V E^2). Other variants include capacity scaling and blocking-flow methods.

Ford-Fulkerson is applicable to domains such as network routing, scheduling, and image segmentation, where maximum flow formulations model constraints.