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 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
| |||