Content deleted Content added
Line 49:
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.
==Push-relabel Algorithm==
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.
| |||