Describe the Ford-Fulkerson algorithm and its application in network flow problems.

Official answer

Ford-Fulkerson is an augmenting-path method for maximum flow. Start with a feasible flow, often zero. In the residual network, find a source-to-sink path, add its bottleneck residual capacity, and update both forward and reverse residual capacities. Reverse edges allow later paths to undo and reroute an earlier choice.

For a unit-capacity matching example, suppose A can use X or Y, while B can use only X. An initial path assigning A to X must be reversible so the next augmentation can move A to Y and assign B to X. Ignoring reverse edges can stop at one match when two are possible.

When no augmenting path exists, vertices reachable from the source in the residual network define a cut whose capacity equals the flow, certifying optimality. With nonnegative integer capacities, each augmentation increases flow by at least one, giving a bound dependent on the maximum flow value. Arbitrary irrational capacities can cause nontermination for unrestricted path choices.

Edmonds-Karp chooses a shortest augmenting path in number of edges using BFS and has O(VE²) time under the standard arithmetic model. Handle numerical precision deliberately. Applications include bipartite matching and capacity allocation; realistic network scheduling may require constraints beyond a single-commodity flow model.