Zatím jsme ukázali odhady na počet provedení operací zvýšení vrcholu a protlačení toku po hraně. Abychom mohli něco tvrdit o časové složitosti, tak ještě musíme upřesnit, jak proběhne nalezení přípustné hrany a jak poznáme, že je čas zvýšit vrchol. O maximum distance push-relabel algoritmu budeme muset ještě ukázat, jak najít aktivní vrchol $v$ s maximálním $d(v)$.

Pozorování: Nechť $v\in V$ je aktivní a hrana $vw$ není přípustná. Před tím, než se hrana $vw$ stane přípustnou, bude muset proběhnout zvýšení vrcholu $v$.
Důkaz: Pokud hrana $vw$ není přípustná, tak buď $d(v)\leq d(w)$ a nebo $r(vw)=0$. Druhý případ se může změnit pouze protlačením toku po opačné hraně $wv$, ale potom bude $d(w)=d(v)+1$. Proto bude v obou případech platit $d(v)\leq d(w)$ a jenom zvýšení vrcholu $v$ to může změnit.

Pro každý vrchol si pamatujeme seznam sousedů $Sousedi(v)$. Zpracování vrcholu $v$ proběhne tak, že postupně projdeme $w\in Sousedi(v)$ a provedeme protlačení po přípustných hranách $vw$. Průchod seznamu sousedů skončí buď tak, že se $v$ stane neaktivním, nebo tím, že dojdeme na konec seznamu $Sousedi(v)$.

V momentě, kdy dorazíme na konec seznamu, tak už z $v$ nevede žádná přípustná hrana a proto zvýšíme $v$. Ke zvýšení vrcholu potřebujeme znát minimum z $d(w)$ pro všechny $w\in Sousedi(v)$. Toto minimum si můžeme počítat už během průchodu seznamu sousedů. Zvýšení vrcholu $v$ dokonce proběhne právě tehdy, když se dostaneme na konec seznamu $Sousedi(v)$.

Když bude $v$ znovu vybrán ke zpracování, tak podle pozorování nemohly od posledního zvýšení $v$ přibýt nové přípustné hrany. Proto při zpracování vrcholu $v$ nemusíme procházet seznam $Sousedi(v)$ od začátku, ale můžeme začít tam, kde jsme naposledy skončili (pro každý vrchol musíme pamatovat aktuální pozici v seznamu sousedů).

Protože každý vrchol můžeme zvýšit nejvýše $2n-1$ krát, tak projdeme seznam sousedů každého vrcholu také nejvýše $2n-1$ krát. Z toho důvodu je celkový čas strávený hledáním přípustných hran roven $\OO(\sum_{v\in V} n\cdot |Sousedi(v)|)=\OO(nm)$. Celkový čas strávený nad zvyšováním vrcholů je stejný.

Celkový čas strávený nad operacemi protlačení je $\OO(N)$, kde $N$ je počet všech protlačení. Čas nalezení dalšího aktivního vrcholu je konstantní, protože nám nezáleží na pořadí aktivních vrcholů a můžeme si je dávat do fronty. Aktivní vrchol hledáme nejvýše tolikrát, kolik je všech operací protlačení a zvýšení vrcholu. Celkem tedy hledání aktivních vrcholů zabere čas $\OO(N+n^2)$ a to je podle věty [ref]thm_push_relabel[/ref] nejvýše $\OO(n^2m)$.

Právě jsme si ukázali, že push-relabel algoritmus může být implementován tak, aby běžel v čase $\OO(n^2m)$.

Podívejme se na případ maximum distance push-relabel algoritmu. Není jasné, jak implementovat výběr aktivního vrcholu s maximálním $d(v)$ tak, aby celkem běžel v čase $\OO(N)$. To v průměru odpovídá konstantnímu času na jednu operaci protlačení. Jednoduché řešení projde všechny vrcholy, ale to trvá čas $\OO(n)$ na jedno nalezení aktivního vrcholu.

Provedeme to jinak. Všechny aktivními vrcholy s $d(v)=k$ si uložíme do fronty $D_k$. Frontu realizujeme jako obousměrný spojový seznam. Ten umožní provádět vkládání a mazání v konstantním čase. Navíc si pro každý vrchol budeme pamatovat ukazatel, který nám umožní přístup k položce ve správné frontě v konstantním čase (pro aktivní vrcholy).

Po provedení zvýšení vrcholu jednoduše přesuneme vrchol do jiné fronty. Pokud protlačení toku po hraně $vw$ aktivuje $w$, tak ho vložíme do správné fronty. Pokud protlačení deaktivuje vrchol $v$, tak ho vyřadíme z fronty. Tyto operace proběhnou v konstantním čase.

Proč je tak jednoduché najít aktivní vrchol s maximálním $d(v)$? Po zvýšení $v$ zůstane vrchol $v$ aktivní a s maximálním $d(v)$. Dejme tomu, že $d(v)=k$. Pokud protlačení po $vw$ deaktivuje $v$, tak se nejprve podíváme do fronty $D_k$. Když je prázdná, tak se podíváme do fronty $D_{k-1}$. Skoro vždy v ní najdeme aktivní vrchol, protože poslední protlačení po $vw$ splňovalo $d(w)=k-1$. Vrchol $w$ musí být aktivní, jinak je $w=s$ nebo $w=t$.

Případ $w=t$ je triviální, protože potom není žádný vrchol aktivní a algoritmus skončí.

Jediný případ, kdy neuspějeme s hledáním aktivního vrcholu, nastane, když zpracujeme vrchol z $D_{n+1}$ a obě fronty $D_{n+1}$, $D_n$ jsou prázdné. Než tato situace nastane znova, tak se bude muset nějaký vrchol dostat do fronty $D_{n+1}$. Neboli jeho $d(v)$ bude muset překročit $n$. To může nastat pro každý vrchol nejvýše jednou a proto tento špatný případ nastane nejvýše $n$ krát. V tomto špatném případě budeme muset prohledat všechny fronty $D_k$ s $k\lt n$. Špatné případy celkem přispějí do hledání aktivních vrcholů časem $\OO(n^2)$. Celkem hledání aktivních vrcholů zabere čas $\OO(N+n^2)$, kde $N$ je počet všech protlačení.

Ukázali jsme si, že maximum distance push-relabel algoritmus může být implementován tak, aby běžel v čase $\OO(n^3)$. Pokud bychom použili odhad $\OO(n^2\sqrt{m})$ na počet protlačení, tak dokonce v čase $\OO(n^2\sqrt{m})$.

Heuristika zrychlující Push-Relabel algoritmus

Ještě zmíníme heuristiku, které nemá vliv na odhad časové složitosti, ale v praxi podstatně zrychlí výpočet. Pravidelně, řekněme po $n/2$ zpracováních vrcholů, přepočítáme platné označkování. Ukazovali jsme si, že platné označkování $d(v)$ je dolním odhadem na $d_f(v,t)$ a že $d(v)-n$ je dolním odhadem $d_f(v,s)$. Zvolme proto nové označkování jako $d(v):=\min\{ d_f(v,t),\; n+d_f(v,s) \}$. Ukažte, že toto označkování je platné a v jistém smyslu nejlepší možné. Také si rozmyslete, jak rychle ho můžeme spočítat.

Poznámka: Předvýpočet platného označkování se vyplatí už při inicializaci push-relabel algoritmu.