Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 21:38, 25 November 2013

Revision as of 14:13, 26 November 2013

Line 9:

The Preflow algorithm relaxes this constraint while it determines the maximum flow of the network, allowing a vertex to have more flow coming

into it than going out. This is called the ''excess'' flow of a vertex, or ''preflow''. Any vertex with excess flow

is known as an ''active vertex''. Excess flow can only be moved down [[residual graph|residual edges]] of the [[residual graph|residual graph]]. Flow is ''pushed'' through the network by adjusting the ''height'' of the vertices. Height is updated and maintained via the concept of a ''valid labelling''. Stated precisely this labelling is <math>h(u) \leq h(v) +1</math>, where ''h(u)'' is height of vertex ''u'', for each residual edge incident to ''u''. In other words a vertex cannot be more than 1 higher from its neighbour on a residual edge (there is no bound on how much lower it can be).

Flow always goes from a higher vertex to a lower vertex.

Line 52:

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.

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|max-flow min-cut theorem]].

===Push===