Content deleted Content added
Line 83:
===Time complexity===
We bound the numbers of relabels, saturating pushes and nonsaturating pushes separately. Because {{nowrap|0 ≤ ''h''(''u'') ≤ 2''n'' − 1}} for every vertex ''u'', and each relabel increases {{nowrap|''h''(''u'')}} by at least one, the total number of relabels on all vertices is {{nowrap|''O''(''V''<sup>2</sup>)}}. Each saturating push on an admissible edge {{nowrap|(''u'', ''v'')}} removes the edge from {{nowrap|''G<sub>f</sub>''}}. For the edge to be reinserted into {{nowrap|''G<sub>f</sub>''}} for another saturating push, ''v'' must be first relabeled, followed by a push on edge {{nowrap|(''v'', ''u'')}}, then ''u'' must be relabeled. In the process, {{nowrap|''h''(''u'')}} increases by at least two. Therefore, there are {{nowrap|''O''(''V'')}} saturating pushes on {{nowrap|(''u'', ''v'')}}, and the total number of saturating pushes on all edges is {{nowrap|''O''(''VE'')}}.
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'')}}.▼
Bounding the number of nonsaturating pushes can be achieved via a [[Potential method|potential argument]]. We use the potential function {{nowrap|Φ {{=}} ∑<sub>''u'' ∈ ''V'' ∧ ''e''(''u'') > 0</sub> ''h''(''u'')}}, i.e., Φ is the sum of the heights of all active vertices. It is obvious that Φ stays nonnegative throughout the execution of the algorithm. Both relabels and saturating pushes can increase Φ. Relabels increase {{nowrap|''h''(''u'')}} by {{nowrap|''O''(''V'')}} for every vertex ''u'' and thus contribute {{nowrap|''O''(''V''<sup>2</sup>)}} increase to Φ. A saturating push on {{nowrap|(''u'', ''v'')}} activates ''v'' if it was inactive before the push, increasing Φ by {{nowrap|''O''(''V'')}}. Hence, the total contribution of all saturating pushes is {{nowrap|''O''(''V''<sup>2</sup>''E'')}}. An unsaturating push on {{nowrap|(''u'', ''v'')}} always deactivates ''u'', but it can also activate ''v'' as in a saturating push. As a result, it decreases Φ by at least {{nowrap|''h''(''u'') − ''h''(''v'') {{=}} 1}}. Since relabels and saturating pushes increase Φ by {{nowrap|''O''(''V''<sup>2</sup> + ''V''<sup>2</sup>''E'') {{=}} ''O''(''V''<sup>2</sup>''E'')}}, the total number of unsaturating pushes is {{nowrap|''O''(''V''<sup>2</sup>''E'')}}.
▲
==Practical implementations==
| |||