Widest augmenting path

ID: widest-augmenting-path

An augmenting path maximizing the possible increase in flow, namely its smallest residual network edge capacity. If the remaining maximum flow is and the original undirected network has edges, a path has bottleneck at least . Otherwise the vertices reachable through arcs of capacity at least define a cut of capacity strictly less than , contradicting the max-flow min-cut theorem. Only one directed arc per original crossing edge contributes to that cut.

New to topics? Read the docs here!