Content deleted Content added
Line 77:
===Correctness===
Because push and relabel operations preserve the validity of preflow ''f'' and height function ''h'', when the algorithm terminates, there are no active vertices other than ''s'' and ''t'', and thus the preflow becomes a valid flow. Since it is also guaranteed throughout that there are no ''s''-''t'' paths in residual network {{nowrap|''G<sub>f</sub>''}}, the algorithm terminates with a maximum flow.
===Time complexity===
It can be shown that the algorithm executes {{nowrap|''O''(''V''<sup>2</sup>)}} relabels, {{nowrap|''O''(''VE'')}} saturating pushes and {{nowrap|''O''(''V''<sup>2</sup>''E'')}} nonsaturating pushes.<ref name="clrs26"/> Data structures can be designed to pick an applicable operation in {{nowrap|''O''(1)}} time. Therefore, the time complexity of the algorithm is {{nowrap|''O''(''V''<sup>2</sup>''E'')}}.
==Relabel-to-Front Algorithm==
| |||