Content deleted Content added
Line 43:
|-
| '''excess(u)''':|| Sum of flow to and from ''u''.
|-
| '''height(u)''':|| Each vertex is assigned a height value. For values <math>\leq |V|</math>, the height serves as an estimate of the distance to the sink node ''t''. For values <math> > |V|</math>, the height is an estimate of the distance back to the sink ''s''.
|}
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.
| |||