Graph Theory37 sections · 1633 units
Open in Course

Vocabulary - Augmenting Path

(Path that increases flow)

An augmenting path is a path from source to sink in the residual graph. It represents an opportunity to increase the total flow. The bottleneck of the path is the minimum residual capacity along it. You can push that much additional flow through the path.

When no augmenting path exists, the flow is maximum. This is the termination condition for Ford-Fulkerson and Edmonds-Karp. The residual graph reveals when you are done.