# Flow augmenting path

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

$LaTeX: f(x, y) \lt U(x, y)$

along all forward arcs, and

$LaTeX: f(x, y) \ge L(x, y)$

along all backward arcs.

The flow, $LaTeX: f<$, is a maximum flow from the source to the sink if and only if there is no flow augmenting path relative to $LaTeX: f$. 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).