Ford–Fulkerson algorithm

The Ford–Fulkerson algorithm finds a maximum flow by repeatedly sending additional flow along paths in a network’s residual graph. Its correctness follows from the augmenting-path principle; termination depends on how augmenting paths are chosen and on capacity values.

Residual graph: A directed graph representing remaining capacity for additional flow and the ability to cancel existing flow. It records which forward and reverse adjustments remain possible after each augmentation.
Flow network: A directed graph with a source, a sink, and a nonnegative capacity assigned to each edge. It is the input structure whose feasible source-to-sink flow the algorithm maximizes.
Edmonds–Karp algorithm: A maximum-flow algorithm that chooses a shortest augmenting path by edge count using breadth-first search. It is Ford–Fulkerson with a specific path rule and a polynomial-time bound.
Bipartite matching problem: The problem of finding the largest set of pairwise nonincident edges in a bipartite graph. Flow reductions let augmenting paths solve this classic matching problem.
Augmenting path: A source-to-sink path in a residual graph whose edges all have positive residual capacity. The algorithm increases flow by the path’s smallest residual capacity.
Maximum flow problem: The problem of finding the greatest feasible flow from a designated source to a sink in a capacitated network. Ford–Fulkerson is a general method for solving this optimization problem.
Dinic's algorithm: A maximum-flow algorithm that sends blocking flows through layered residual graphs. It replaces one-path-at-a-time augmentation with batches of path flow.
Circulation problem: The problem of assigning flows to a network’s edges while satisfying conservation and capacity constraints, often with lower bounds. Maximum-flow methods extend to feasibility and circulation through network transformations.
Bottleneck capacity: The minimum capacity available along a path, limiting how much flow can pass through it. It determines the maximum amount added during one augmentation.
Minimum cut: A partition of a network’s vertices into source and sink sides, with capacity equal to edges crossing between them. A minimum cut provides an upper bound that matches the maximum flow value.

Linked from 9 pages