Content deleted Content added
→"Current-edge" data structure and discharge operation: `else' is necessary. Don't move to the next neighbor if F[u][v] < C[u][v] |
|||
Line 132:
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̃'' < {{!}}''V''{{!}}}} for which there is no vertex ''u'' such that {{nowrap|''h''(''u'') {{=}} ''h̃''}}, then any vertex ''u'' with {{nowrap|''h̃'' < ''h''(''u'') < {{!}}''V''{{!}}}} has been disconnected from ''t'' and can be relabeled to {{nowrap|({{!}}''V''{{!}} + 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
==Sample implementations==
| |||