Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 00:18, 13 January 2010

Revision as of 00:18, 13 January 2010

Line 2:

==Algorithm==

Given a flow network <math>G(V,E)</math> with capacity from node ''u'' to node ''v'' given as <math>c(u,v)</math>, source ''s'' and sink ''t'', we want to find the maximum amount of flow you can send from ''s'' to ''t'' through the network. Two types of operations are performed on nodes, ''push'' and ''relabel''. Throughout we maintain:

* <math>f(u,v)</math>. Flow from ''u'' to ''v''. Available capacity is <math>c(u,v) - f(u,v)</math>.

* <math>height(u)</math>. We only ''push'' from ''u'' to ''v'' if <math>height(u) > height(v)</math>. For all ''u'', <math>height(u)</math> is a non-negative integer.

* <math>excess(u)</math>. Sum of flow to and from ''u''.

After each step of the algorithm, the flow is a '''preflow''', satisfying:

* <math>\ f(u,v) \leq c(u,v)</math>. The flow between <math>u</math> and <math>v</math>, does not exceed the capacity.

* <math>\ f(u,v) = - f(v,u)</math>. We maintain the net flow.

* <math>\ \sum_v f(v,u) = excess(u) \geq 0</math> for all nodes <math>u \neq s</math>. Only the source may produce flow.

Notice that the last condition for a preflow is relaxed from the corresponding condition for a [[Network flow#Definition|legal flow]] in a regular flow network.