🌊 Ford-Fulkerson Max Flow

How It Works

Ford-Fulkerson finds the maximum flow from source S to sink T by repeatedly discovering augmenting paths through a residual graph and pushing flow along them.

• Residual graph — for every forward edge (u→v) with capacity c and current flow f, we maintain a forward residual edge with remaining capacity c-f and a backward edge with capacity f (allowing "undo").
• Augmenting path — any path from S to T in the residual graph. The flow pushed equals the minimum residual capacity along the path (bottleneck).
• BFS (Edmonds-Karp) always picks the shortest augmenting path, guaranteeing O(VE²) time.
• DFS (Ford-Fulkerson) picks an arbitrary path, which may be faster in practice but has worse worst-case complexity with irrational capacities.
• The algorithm terminates when no augmenting path exists. By the max-flow min-cut theorem, the result equals the minimum cut capacity separating S from T.