Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 21:17, 25 November 2013

Revision as of 21:26, 25 November 2013

Line 14:

To ''push'' preflow is to move it down a residual edge from a vertex ''u'' to a vertex ''v'', where <math>h(u) = h(v)+1 </math>. It is called a ''saturating push'' if all of the capacity of the residual edge was used (and thus the edge ''(u,v)'' is removed from the residual graph). It is called a ''non-saturating push'' if after the push there is still available capacity on edge ''(u,v)''. Note that a non-saturating push will deplete all the excess flow from vertex ''u''. A saturating push may deplete ''u'', but not necessarily.

==AlgorithmDefinition==

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:

Line 39:

We observe that the longest possible path from ''s'' to ''t'' is <math>|V|</math> nodes long. Therefore it must be possible to assign ''height'' to the nodes such that for any legal flow, <math>\mathrm{height}(s) = |V|</math> and <math>\mathrm{height}(t) = 0</math>, and if there is a positive flow from ''u'' to ''v'', <math>\mathrm{height}(u) > \mathrm{height}(v)</math>. As we adjust the height of the nodes, the flow goes through the network as water through a landscape. Differing from algorithms such as [[Ford–Fulkerson algorithm|Ford–Fulkerson]], the flow through the network is not necessarily a legal flow throughout the execution of the algorithm.

==Algorithm==

In short words, theThe heights of nodes (except ''s'' and ''t'') of active vertices is adjusted,raised andjust flowenough isto sentsend betweenflow nodesinto 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]].