Content deleted Content added
Line 14:
The number of times each edge is saturated is <math>O(V)</math>. We know that if <math>uv</math> is saturated when sending flow along a path, flow must be sent in the opposite direction, on <math>vu</math> on a second path, before flow can be sent on <math>uv</math> again, on a third path. The first path must be shorter than the second, which again must be shorter than the third. For each edge, the series of augmenting paths which saturated it have strictly increasing length. Since paths do not have cycles, their length is <math>O(V)</math>. Hence the number of saturating sends on an edge is <math>O(V)</math>.
Each time a path is found, at least one of the <math>E</math> edges is saturated. Since each edge is saturated <math>O(V)</math> times, the maximum flow is found in <math>O(VE)</math> rounds. As the cost of a breadth-first-search is <math>O(V+E)</math>, the total running time is <math>O(VE^2)</math> (if <math>E<V</math> we can remove the unused nodes in O(V) first).
==Sample implementation==
| |||