# Flow augmenting path

### From Glossary

This arises in the Ford-Fulkerson labeling algorithm to find a maximum flow in a network with arc flow bounds, and . Given a flow, , from a source to a sink, a flow augmenting path, relative to , is a path from that source to the sink such that

along all forward arcs, and

along all backward arcs.

The flow, , is a maximum flow from the source to the sink if and only if there is no flow augmenting path relative to . If there is a flow augmenting path, it can be changed along the path such that total flow increases (by at least 1 if all data are integer).