Augmenting path

An augmenting path is a source-to-sink path in a flow network’s residual graph whose edges have positive residual capacity. Increasing flow along it raises the total flow.

Residual graph: A directed graph encoding the remaining capacity to increase or decrease flow on network edges. An augmenting path is defined by traversing this graph’s positive-capacity edges.
Ford–Fulkerson algorithm: A family of methods that repeatedly augments flow along residual source-to-sink paths until none remain. Its defining step is finding and using an augmenting path.
Flow: A nonnegative assignment of quantities to a network’s directed edges that respects capacities and conservation. An augmenting path changes a feasible flow while keeping its constraints.
Shortest augmenting path: An augmenting path with the fewest edges among all available residual source-to-sink paths. Edmonds–Karp always selects this path, unlike unrestricted Ford–Fulkerson.
Residual capacity: The amount by which flow on an edge can still be increased in a specified direction. The path’s bottleneck residual capacity sets its maximum possible flow increase.
Edmonds–Karp algorithm: A maximum-flow algorithm that implements Ford–Fulkerson by choosing shortest residual paths with breadth-first search. It specifies a systematic rule for selecting augmenting paths.
Directed path: A sequence of directed edges connecting successive vertices from a starting vertex to an ending vertex. An augmenting path is a directed path from the network’s source to its sink.
Greedy algorithm: An algorithmic strategy that repeatedly makes locally preferred choices without necessarily reconsidering them. Augmenting paths can use reverse edges to revise earlier flow choices rather than commit irreversibly.
Flow network: A directed graph with edge capacities, a source, and a sink, used to model transferable quantities. The path operates within this capacity-constrained structure.
Dinic's algorithm: A maximum-flow algorithm that repeatedly builds level graphs and sends blocking flows through them. Its blocking flows combine many shortest augmenting paths in each phase.

Linked from 15 pages