Content deleted Content added
Line 32:
In short words, the heights of nodes (except ''s'' and ''t'') is adjusted, and flow is sent between nodes, 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===
A ''push'' from ''u'' to ''v'' means sending a part of the excess flow into ''u'' on to ''v''. Three conditions must be met for a ''push'' to take place:
* ''u'' is active, that is <math>\mathrm{excess}(u) > 0</math>. More flow into the node than out of it so far.
* <math>c(u,v) - f(u,v) > 0</math>. Available capacity from ''u'' to ''v''.
* <math>\mathrm{height}(u) = \mathrm{height}(v)+1</math>. Can only send to lower node.
| |||