|
To see that a relabel operation on vertex ''u'' preserves the validity of {{nowrap|''h''(''u'')}}, notice that this is trivially guaranteed by definition for the out-edges of ''u'' in {{nowrap|''G<sub>f</sub>''}}. For the in-edges of ''u'' in the {{nowrap|''G<sub>f</sub>''}}, the increased {{nowrap|''h''(''u'')}} can only satisfy the constraints less tightly but not violate them.
==PushThe generic push-relabel Algorithmalgorithm==
===Description===
The heights of active vertices are raised just enough to send flow into neighbouring vertices, until all possible flow has reached ''t''. Then we continue increasing the height of internal nodes until all the flow that went into the network, but did not reach ''t'', has flowed back into ''s''. A node can reach the height <math>2|V|-1</math> before this is complete, as the longest possible path back to ''s'' excluding ''t'' is <math>|V|-1</math> long, and <math>\mathrm{height}(s) = |V|</math>. The height of ''t'' is kept at 0.
Since {{nowrap|''h''(''s'') {{=}} {{!}}''V''{{!}}}}, {{nowrap|''h''(''t'') {{=}} 0}}, and there is not path longer than {{nowrap|({{!}}''V''{{!}} − 1)}} in {{nowrap|''G<sub>f</sub>''}}, in order for {{nowrap|''h''(''s'')}} to satisfy the valid labeling condition, ''s'' must be disconnected from ''t''. At initialization, the algorithm fulfills this requirement by creating a preflow ''f'' that saturates all out-edges of ''s'', after which {{nowrap|''h''(''u'') {{=}} 0}} is trivially valid for all {{nowrap|''v'' ∈ ''V'' \ {''s'', ''t''}}}.
After initialization, the algorithm repeatedly executes an applicable push or relabel operation until no such operations apply, at which point the preflow has been converted into a maximum flow.
Once we move all the flow we can to ''t'', there is no more path in the residual graph from ''s'' to ''t'' (in fact this is true as soon as we saturate the min-cut). This means that once the remaining excess flows back to ''s'' not only do we have a legal flow, but we have a maximum flow by the [[max-flow min-cut theorem]]. The algorithm relies on two functions:
Algorithm Pushgeneric-push-relabel(G(V, E), s, t) :▼
===Push===
create a preflow f that saturates all out-edges of s
A ''push'' from ''u'' to ''v'' means sending as much excess flow from ''u'' to ''v'' as we can. Three conditions must be met for a ''push'' to take place:
let h[u] = 0 ∀v ∈ V
:{|
while there is an applicable push or relabel operation
| <math>u</math> is active || Or <math>\mathrm{excess}(u) > 0</math>. There is more flow entering than exiting the vertex.
execute the operation
|-
| <math>r(u,v) > 0</math> || There is a residual edge <math>r(u,v)</math> from ''u'' to ''v'', where <math>r(u,v) = c(u,v) - f(u,v)</math>
|-
| style = "width:300px" | <math>\mathrm{height}(u) = \mathrm{height}(v)+1</math> || ''u'' is higher than ''v''.
|}
===Correctness===
If all these conditions are met we can execute a ''Push'':
Because push and relabel operations preserve the validity of preflow ''f'' and height function ''h'', when the algorithm terminates, there are no active vertices, and thus the preflow becomes a valid flow. Since it is also guaranteed throughout that there are no ''s''-''t'' paths in residual network {{nowrap|''G<sub>f</sub>''}}, the algorithm terminates with a maximum flow.
Function Push(u,v)
flow = min(excess(u), c(u,v)-f(u,v));
excess(u) -= flow; // subtract the amount of flow moved from the current vertex
excess(v) += flow; // add the flow to the vertex we are pushing to
f(u,v) += flow; // add the amount of flow moved to the flow across the edge ''(u,v)''
f(v,u) -= flow; // subtract the flow from the edge in the other direction.
===Relabel===
When we ''relabel'' a node ''u'' we increase its height until it is 1 higher than its lowest neighbour in the residual graph. Conditions for a ''relabel'':
:{|
| <math>u</math> is ''active'' ||
|-
| <math>\mathrm{height}(u) \leq \mathrm{height}(v)</math> where <math> r(u,v) > 0</math>
|}
So we have excess flow to push, but we are not higher than any of our neighbours that have available capacity across their edge. Then we can execute '''Relabel''':
Function Relabel(u)
height(u) = min(height(v) where r(u,v) > 0) + 1;
===Push–relabel algorithm===
The generic ''Push–relabel algorithm'' has the following structure:
▲ Algorithm Push-relabel(G(V,E),s,t)
while ''push'' or ''relabel'' are legal: //in other words while there is excess in the network
Perform a legal push, or
perform a legal relabel;
Executing these two functions in any order, so long as there remains any active vertices results in termination of the algorithm in a maximum flow. The running time for these algorithms when not observing any order to the Push and Relabel operations is <math>O(V^2 E)</math> (argument omitted). The bottleneck is the number of non-saturating pushes.
==Relabel-to-Front Algorithm==
| 