Overview
Ford-Fulkerson is a general method for computing a maximum flow in a capacitated directed network. It begins with zero flow and repeatedly searches for a path from the source to the sink in the residual graph. The algorithm sends additional flow along the path, limited by the smallest residual capacity on that path. It stops when no augmenting path exists.
Key concepts
name: Augmenting Path; description: A source-to-sink path in the residual network along which additional flow can be sent.; name: Bottleneck Capacity; description: The smallest residual capacity among the edges of an augmenting path. It determines the maximum amount that can be added along that path.; name: Residual Graph; description: A graph representing remaining forward capacity and the ability to cancel previously sent flow through reverse edges.; name: Reverse Edge; description: An edge in the residual network that allows some previously assigned flow to be canceled or rerouted.
Complexity
integerCapacities: O(E × F) for a standard augmenting-path implementation, where E is the number of edges and F is the maximum flow value.; space: O(V + E) for a typical adjacency-list residual network.; importantNote: The running time depends on the method used to find augmenting paths. With arbitrary real capacities, a poor path-selection strategy can fail to terminate in certain cases.
Example
scenario: A network has a source S, intermediate vertices A and B, and a sink T.; description: The algorithm finds a valid path from S to T, identifies the smallest remaining capacity on that path, and sends that amount of flow.; illustration: If a path has residual capacities 8, 5, and 7, its bottleneck capacity is 5. The algorithm can augment the flow along that path by 5 units.; nextStep: The residual network is updated, and another augmenting path may become available.
Pseudocode
FORD-FULKERSON(G, s, t):
initialize flow to 0 on every edge
while an augmenting path P exists from s to t in the residual graph:
bottleneck = minimum residual capacity on P
for each edge (u, v) in P:
update flow using bottleneck
update forward and reverse residual capacities
return total flow leaving s
Applications
Transportation network analysis.; Resource distribution.; Communication network capacity analysis.; Matching and assignment problems.; Supply chain planning.
Advantages
Conceptually simple and based on repeated path searches.; Works with a wide range of network structures.; Provides a foundation for understanding maximum flow algorithms.; Can be effective for small networks and suitable capacity values.