FordFulkerson

The Ford-Fulkerson method is an algorithm for computing the maximum flow in a flow network. Introduced by L. R. Ford Jr. and D. R. Fulkerson in 1956, it begins with zero flow and repeatedly searches for an augmenting path from the source to the sink in the residual network and increases the flow along that path by the path's bottleneck capacity.

The residual graph represents remaining capacities: for each edge (u,v) with capacity c(u,v) and current flow f(u,v), the residual capacity is c_f(u,v) = c(u,v) - f(u,v); a reverse edge (v,u) with capacity f(u,v) allows undoing flow. An s-t path in the residual graph allows pushing an amount equal to the minimum residual capacity along the path, after which the corresponding forward and reverse edges are updated.

Termination and theory: The process terminates when no s-t path exists in the residual graph, at which point the achieved flow is maximum. The maximum flow equals the minimum cut, per the max-flow min-cut theorem. If all capacities are integers, the algorithm terminates after a finite number of augmentations, though the number can be exponential in the worst case. A common variant, Edmonds-Karp, always chooses the shortest augmenting path (via BFS), yielding a time complexity of O(VE^2).

Applications and notes: Ford-Fulkerson serves as a foundational method for network flow problems and underpins many algorithms for routing, scheduling, and matching problems.