Content deleted Content added
Line 126:
The algorithm has {{nowrap|''O''(''V''<sup>2</sup>{{sqrt|''E''}})}} time complexity. If the lowest-label selection rule is used instead, the time complexity becomes {{nowrap|''O''(''V''<sup>2</sup>''E'')}}.<ref name="ahuja97"/>
===Implementation techniques===
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"/>
Heuristics are crucial to improving the empirical performance of the algorithm.<ref name="cherkassky95"/> Two commonly used heuristics are the gap heuristic and the global relabeling heuristic.<ref name="goldberg86"/><ref name="derigs89"/> The gap heuristic detects gaps in the height function. If there is a height {{nowrap|0 < ''h̃'' < ''n''}} for which there is no vertex ''u'' such that {{nowrap|''h''(''u'') {{=}} ''h̃''}}, then any vertex ''u'' with {{nowrap|''h̃'' < ''h''(''u'') < ''n''}} has been disconnected from ''t'' and can be relabeled to {{nowrap|(''n'' + 1)}} immediately. The global relabeling heuristic periodically performs backward breadth-first search from ''t'' in {{nowrap|''G<sub>f</sub>''}} to compute the exact heights of the vertices. Both heuristics skips unhelpful relabel operations, which are a bottleneck of the algorithm and contribute to the ineffectiveness of dynamic trees.<ref name="goldberg08"/>
==Sample implementations==
| |||