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!