Content deleted Content added
Line 26:
{{nowrap|''e''(''s'')}} is assumed to be infinite. A vertex ''u'' is called ''active'' if {{nowrap|''e''(''u'') > 0}}.
For each {{nowrap|(''u'', ''v'') ∈ ''V'' × ''V''}}, denote its ''residual capacity'' by {{nowrap|''c<sub>f</sub>''(''u'', ''v'') {{=}} ''c''(''u'', ''v'') − ''f''(''u'', ''v'')}}. The residual network of ''G'' with respect to a preflow ''f'' is defined as {{nowrap|''G<sub>f</sub>''(''V'', ''E<sub>f</sub>'')}} where {{nowrap|''E<sub>f</sub>'' {{=}} {(''u'', ''v'') {{!}} ''u'', ''v'' ∈ ''V'' ∧ ''c<sub>f</sub>''(''u'', ''v'') > 0}}}. If there is no path from any active vertex to ''t'' in {{nowrap|''G<sub>f</sub>''}}, the preflow is called ''maximum''. In a maximum preflow, the excess of ''t'' is equal to the value of a maximum flow; if ''T'' is the set of vertices from which ''t'' is reachable in {{nowrap|''G<sub>f</sub>''}}, and {{nowrap|''S'' {{=}} ''V'' \ ''T''}}, then {{nowrap|(''S'', ''T'')}} is a [[Max-flow min-cut theorem|minimum ''s''-''t'' cut]].
The push-relabel algorithm makes use of distance labels, or ''heights'', of the vertices denoted by {{nowrap|''h''(''u'')}}. For each vertex {{nowrap|''u'' ∈ ''V'' \ {''s'', ''t''}}}, {{nowrap|''h''(''u'')}} is a nonnegative integer satisfying
| |||