Ford–Fulkerson algorithm

Summary

The Ford–Fulkerson algorithm computes a maximum flow from a source to a sink in a flow network. It starts from the zero flow and repeatedly pushes extra flow along an augmenting path. This is a path from source to sink in the residual network that still has spare capacity. When no augmenting path is left, the flow is maximum, and this argument also proves the max-flow min-cut theorem. With integer capacities it terminates and produces an integer maximum flow.