Content deleted Content added
Line 127:
===Implementation techniques===
Although in the description of the generic push-relabel algorithm above, {{nowrap|''h''(''u'')}} is set to zero for each vertex ''u'' other than ''s'' and ''t'' at the beginning, it is preferable to perform a backward [[breadth-first search]] from ''t'' to compute the exact heights.<ref name="goldberg86"/>
The algorithm is typically separated into two phases. Phase one computes a maximum preflow by discharging only active vertices whose heights are below ''n''. Phase two converts the maximum preflow into a maximum flow by returning excess flow that cannot reach ''t'' to ''s''. It can be shown that phase two has {{nowrap|''O''(''VE'')}} time complexity regardless of the order of push and relabel operations and is therefore dominated by phase one. Alternatively, it can be implemented using flow decomposition.<ref name="amo93"/>
| |||