Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 20:41, 25 November 2013

Revision as of 20:46, 25 November 2013

Line 80:

In the ''relabel-to-front algorithm'', the order of the ''push'' and ''relabel'' operations is given:

# For each edge incident to <math>s, (s,v)</math>, push flow from ''s'' equal to <math>c(s,v)</math> (saturate the edge).

# Send as much flow from ''s'' as possible.

# Build a list <math>L</math> of all vertices except ''s'' and ''t''.

# For each <math> u \in L</math>:

Line 88:

### Restart the traversal from the element following ''u'' in ''L''.

The running time for ''relabel-to-front'' is <math>O(V^3)</math> (proof omitted). Again the bottleneck is non-saturating pushes, but we have reduced the number. Not that after step 1 there is no path from ''s'' to ''t'' in the residual graph.

==Sample implementation==