FLOW AUGMENTING PATH

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

f(x, y) < U(x, y) along all forward arcs;   f(x, y) > L(x, y) along all backward arcs. The flow, f, is a maximum flow from the source to the sink if, and only if, there is no flow augmenting path relative to 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).