Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 20:32, 26 November 2013

Revision as of 20:41, 26 November 2013

Line 75:

===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'':

* ''u'' is ''active'', that is <math>\mathrm{excess}(u) > 0</math>.

:{|

* <math>\mathrm{height}(u) \leq \mathrm{height}(v)</math> for all ''v'' such that <math>c(u,v)-f(u,v) > 0</math>. The only nodes we have available capacity to are higher.

| <math>u</math> is ''active'' ||

When relabelling ''u'', we set <math>\mathrm{height}(u)</math> to be 1 greater than its lowest neighbour ''v'' where <math>c(u,v)-f(u,v) > 0</math>.

|-

*| <math>\mathrm{height}(u) \leq \mathrm{height}(v)</math> for all ''v'' such thatwhere <math>c(u,v)-f r(u,v) > 0</math>. The only nodes we have available capacity to are higher.

|}

So we have excess flow to push, but we 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===