Content deleted Content added
Nils Grimsmo (talk | contribs) Category: Network flow |
Nils Grimsmo (talk | contribs) →Complexity: Useless explanation |
||
Line 4:
The algorithm is identical to the [[Ford-Fulkerson algorithm]], except that the search order when finding the augmenting path is defined. The path found must be the shortest path which has available capacity.
<!--
This argument is so incomplete and hard to understand that we better leave it out until somebody write a new one. The one in Introduction to algorithms is nice.
==Complexity==
Line 15 ⟶ 18:
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==
| |||