Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 20:51, 26 November 2013

Revision as of 21:01, 26 November 2013

Line 125:

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

Function Relabel-to-Front(G(V,E),s,t):

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

for each edge (s,v):

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

push(s,v); //note that this will saturate the edge

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

L = v - {''s'',''t''}; //build a list of all vertices in any order

## ''Discharge'' the current vertex ''u''.

current = L.head;

## If the height of ''u'' has changed:

while (current != NIL):

### Move ''u'' to the front of the list ''L''

old_height = height(u);

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

discharge(u);

if height(u) > old_height:

### Move ''u'' to the front of the list ''L''

current = current.next;

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. Note that after step 1 there is no path from ''s'' to ''t'' in the residual graph.