Ford-Fulkerson
Repeatedly find any augmenting path from s to t in residual graph. Push flow along it. Terminate when no path.
Advertisement
Residual graph
For each edge (u,v) with capacity c and flow f: forward residual c-f, backward residual f. Path uses residual capacities.
Advertisement
Max-flow min-cut
Max flow value = min s-t cut capacity. Fundamental duality.
Complexity
O(E × f) where f = max flow. Integer capacities. Can be arbitrarily slow for irrational capacities.