\input ../sgr.tex

\prednaska{13}{Nejkratší cesty}{}

\def\ppsp{1-1}
\def\sssp{1-$n$}
\def\apsp{$n$-$n$}
\def\astar{A\kern-0.15em *}

Problém hledání nejkratší cesty v~(obvykle ohodnoceném orientovaném) grafu
provází teorii grafových algoritmů od~samých počátků. Základní algoritmy
pro hledání cest jsou nedílnou součástí základních kursů programování
a algoritmů, my se budeme věnovat zejména různým jejich vylepšením.

Uvažujme tedy nějaký orientovaný graf, jehož každá hrana~$e$ je opatřena
{\I délkou} $\ell(e)\in{\bb R}$. Množině hran (třeba sledu nebo cestě)
pak přiřadíme délku rovnou součtu délek jednotlivých hran.

Pro vrcholy $u,v$ definujeme jejich {\I vzdálenost} $d(u,v)$ jako nejmenší
možnou délku cesty z~$u$ do~$v$ (jelikož cest je v~grafu konečně mnoho,
minimum vždy existuje). Pokud z~$u$ do~$v$ žádná cesta nevede, položíme
$d(u,v) := \infty$.

Obvykle se studují následující tři problémy:

\itemize\ibull
\:{\bo 1-1} neboli {\bo P2PSP} (Point to Point Shortest Path) -- chceme nalézt nejkratší
  cestu z~daného vrcholu~$u$ do~daného vrcholu~$v$. (Pokud je nejkratších cest
  více, tak libovolnou z~nich.)
\:{\bo 1-n} neboli {\bo SSSP} (Single Source Shortest Paths) -- pro daný vrchol~$u$ chceme
  nalézt nejkratší cesty do~všech ostatních vrcholů.
\:{\bo n-n} neboli {\bo APSP} (All Pairs Shortest Paths) -- zajímají nás nejkratší cesty
  mezi všemi dvojicemi vrcholů.
\endlist

Překvapivě, tak obecně, jak jsme si uvedené problémy definovali, je neumíme
řešit v~polynomiálním čase: pro grafy, které mohou obsahovat hrany záporných
délek bez jakýchkoliv omezení, je totiž hledání nejkratší cesty NP-těžké
(lze na~něj snadno převést existenci hamiltonovské cesty). Všechny známé
polynomiální algoritmy totiž místo nejkratší cesty hledají nejkratší sled
-- nijak nekontrolují, zda cesta neprojde jedním vrcholem vícekrát.

Naštěstí pro nás je to v~grafech bez cyklů záporné délky totéž: pokud se
v~nalezeném sledu vyskytne cyklus, můžeme jej \uv{vystřihnout} a tím získat
sled, který není delší a~který má méně hran. Každý nejkratší sled tak
můžeme upravit na~stejně dlouhou cestu.
V~grafech bez záporných cyklů je tedy jedno, zda hledáme sled nebo cestu;
naopak vyskytne-li se záporný cyklus dosažitelný z~počátečního vrcholu,
nejkratší sled ani neexistuje.

Navíc se nám bude hodit, že každý prefix nejkratší cesty je opět nejkratší
cesta. Jinými slovy pokud některá z~nejkratších cest z~$u$ do~$v$ vede
přes nějaký vrchol~$w$, pak její část z~$u$ do~$w$ je jednou z~nejkratších
cest z~$u$ do~$w$. (V~opačném případě bychom mohli úsek $u\ldots w$ vyměnit za~kratší.)

Díky této {\I prefixové vlastnosti} můžeme pro každý vrchol~$u$ sestrojit jeho {\I strom
nejkratších cest}~${\cal T}(u)$. To je nějaký podgraf grafu~$G$, který má tvar
stromu zakořeněného v~$u$ a orientovaného směrem od~kořene, a~platí pro něj, že
pro každý vrchol~$v$ je (jediná) cesta z~$u$ do~$v$ v~tomto stromu jednou
z~nejkratších cest z~$u$ do~$v$ v~původním grafu.

\s{Pozorování:} Strom nejkratších cest vždy existuje.

\proof
Nechť $u=v_1,\ldots,v_n$ jsou všechny vrcholy grafu~$G$. Indukcí budeme
dokazovat, že pro každé~$i$ existuje strom~${\cal T}_i$, v~němž se nacházejí nejkratší
cesty z~vrcholu~$u$ do vrcholů $v_1,\ldots,v_i$. Pro $i=1$ stačí uvážit
strom obsahující jediný vrchol~$u$. Ze~stromu ${\cal T}_{i-1}$ pak vyrobíme
strom ${\cal T}_i$ takto: Nalezneme v~$G$ nejkratší cestu z~$u$ do~$v_i$
a označíme~$z$ poslední vrchol na~této cestě, který se ještě vyskytuje v~${\cal T}_{i-1}$.
Úsek nejkratší cesty od~$z$ do~$v_i$ pak přidáme do~${\cal T}_{i-1}$
a díky prefixové vlastnosti bude i cesta z~$u$ do~$v_i$ v~novém stromu
nejkratší.
\qed

Zbývá se dohodnout, v~jakém tvaru mají naše algoritmy vydávat výsledek.
U~problémů typu \ppsp{} je nejjednodušší vypsat celou cestu, u~\sssp{} můžeme jako výstup
vydat strom nejkratších cest z~daného počátku (všimněte si, že stačí
uvést předchůdce každého vrcholu), u~\apsp{} vydáme strom nejkratších cest
pro každý ze~zdrojových vrcholů.

Často se ovšem ukáže, že podstatná část problému se skrývá v~samotném
výpočtu vzdáleností a sestrojení předchůdců je triviálním rozšířením algoritmu.
Budeme tedy obvykle jen počítat vzdálenosti a samotnou rekonstrukci cest
ponecháme čtenáři jako snadné cvičení.

\h{Relaxační algoritmus}

Začněme problémem \sssp{} a označme~$u$ výchozí vrchol. Většina známých
algoritmů funguje tak, že pro každý vrchol~$v$ udržují ohodnocení $h(v)$,
které v~každém okamžiku odpovídá délce nějakého sledu z~$u$ do~$v$. Postupně
toto ohodnocení upravují, až se z~něj stane vzdálenost $d(u,v)$ a algoritmus
se může zastavit.

Vhodnou operací pro vylepšování ohodnocení je takzvaná {\I relaxace.}
Vybereme si nějaký vrchol~$v$ a pro všechny jeho sousedy~$w$ spočítáme
$h(v) + \ell(v,w)$, tedy délku sledu, který vznikne rozšířením aktuálního
sledu do~$v$ o~hranu $(v,w)$. Pokud je tato hodnota menší než~$h(w)$,
tak jí $h(w)$ přepíšeme.

Abychom zabránili opakovaným relaxacím téhož vrcholu, které nic nezmění,
budeme rozlišovat tři stavy vrcholů: {\I neviděn} (ještě jsme ho nenavštívili),
{\I otevřen} (změnilo se ohodnocení, časem chceme relaxovat) a {\I uzavřen}
(už jsme relaxovali a není potřeba znovu).

Náš algoritmus bude fungovat následovně:

\algo
\:$h(*)\leftarrow \infty$, $h(u)\leftarrow 0$.
\:$\<stav>(*)\leftarrow\<neviděn>$, $\<stav>(u)\leftarrow\<otevřen>$.
\:Dokud existují otevřené vrcholy, opakujeme:
\::$v\leftarrow\hbox{libovolný otevřený vrchol}$.
\::$\<stav>(v)\leftarrow\<uzavřen>$.
\::Relaxujeme~$v$:
\:::Pro všechny hrany $vw$ opakujeme:
\::::Je-li $h(w) > h(v) + \ell(v,w)$:
\:::::$h(w)\leftarrow h(v) + \ell(v,w)$.
\:::::$\<stav>(w)\leftarrow\<otevřen>$.
\:Vrátíme výsledek $d(u,v)=h(v)$ pro všechna~$v$.
\endalgo

Podobně jako u~minimálních koster, i zde se jedná o~meta-algoritmus, protože
v~kroku~4 nespecifikuje, který z~otevřených vrcholů vybírá. Přesto
ale můžeme dokázat několik zajímavých tvrzení, která na~konkrétním způsobu
výběru nezávisejí.

\s{Věta:} Spustíme-li meta-algoritmus na graf bez záporných cyklů, pak:

\numlist\nparen
\:Ohodnocení $h(v)$ vždy odpovídá délce nějakého sledu z~$u$ do~$v$.
\:$h(v)$ dokonce odpovídá délce nějaké cesty z~$u$ do~$v$.
\:Algoritmus se vždy zastaví.
\:Po zastavení jsou označeny jako uzavřené právě ty vrcholy, které jsou dosažitelné z~$u$.
\:Po zastavení mají konečné~$h(v)$ právě všechny uzavřené vrcholy.
\:Pro každý dosažitelný vrchol je na~konci $h(v)$ rovno $d(u,v)$.
\endlist

\proof

\numlist\nparen
\:Dokážeme indukcí podle počtu kroků algoritmu.
\:Stačí rozmyslet, v~jaké situaci by vytvořený sled mohl obsahovat cyklus.
\:Cest, a~tím pádem i možných hodnot~$h(v)$ pro každý~$v$, je konečně mnoho.
\:Implikace $\Rightarrow$ je triviální, pro $\Leftarrow$ stačí uvážit neuzavřený vrchol,
  který je dosažitelný z~$u$ cestou o~co nejmenším počtu hran.
\:$h(v)$ nastavujeme na~konečnou hodnotu právě v~okamžicích, kdy se vrchol stává otevřeným.
  Každý otevřený vrchol je časem uzavřen.
\:Kdyby tomu tak nebylo,
  vyberme si ze~\uv{špatných} vrcholů~$v$ takový, pro nějž obsahuje nejkratší cesta z~$u$ do~$v$
  nejmenší možný počet hran. Vrchol~$v$ je zajisté různý od~$u$, takže má na~této cestě nějakého
  předchůdce~$w$. Přitom~$w$ už musí být ohodnocen správně a relaxace, která mu toto ohodnocení
  nastavila, ho musela prohlásit za~otevřený. Jenže každý otevřený vrchol je později uzavřen,
  takže~$w$ poté musel být ještě alespoň jednou relaxován, což muselo snížit~$h(v)$ na správnou
  vzdálenost.
\qeditem
\endlist

\>Dokázali jsme tedy, že meta-algoritmus pro libovolnou implementaci kroku~4
spočítá správné vzdálenosti.

\medskip

\s{Cvičení:}
\itemize\ibull
\:Nechť do algoritmu doplníme udržování předchůdců tak, že v~kroku~9
  přenastavíme předchůdce vrcholu~$w$ na vrchol~$v$. Dokažte, že předchůdci
  dosažitelných vrcholů budou tvořit strom a že tento strom bude stromem
  nejkratších cest z~vrcholu~$u$.
\:Dokažte, že pro graf, v~němž je alespoň jeden záporný cyklus dosažitelný
  z~počátečního vrcholu, se algoritmus nezastaví a ohodnocení všech vrcholů
  na cyklu postupně klesnou libovolně hluboko. Nedosažitelné záporné cykly
  chod algoritmu samozřejmě nijak neovlivní.
\endlist

\h{Bellmanův-Fordův-Mooreův algoritmus}

Bellman \cite{bellman:bfm}, Ford \cite{ford:bfm} a Moore objevili nezávisle na sobě algoritmus (říkejme mu BFM),
který lze v~řeči našeho meta-algoritmu formulovat takto: Otevřené vrcholy
udržujeme ve~frontě (vždy relaxujeme vrchol na počátku fronty, nově otevírané
zařazujeme na~konec). Co toto pravidlo způsobí?

\s{Věta:} Časová složitost algoritmu~BFM činí $\O(nm)$.

\proof
Běh algoritmu rozdělíme na~fáze. Nultá fáze sestává z~vložení vrcholu~$u$
do~fronty. V~$(i+1)$-ní fázi relaxujeme ty vrcholy, které byly do~fronty
uloženy během $i$-té fáze.

Jelikož relaxace vrcholu trvá lineárně se stupněm vrcholu a každý vrchol
se dané fáze účastní nejvýše jednou, trvá jedna fáze $\O(m)$. Zbývá ukázat,
že fází provedeme nejvýše~$n$.

Indukcí dokážeme, že na konci $i$-té fáze je každé ohodnocení $h(v)$ shora omezeno
délkou nejkratšího z~$uv$-sledů o~nejvýše~$i$ hranách. Pro $i=0$ to triviálně
platí. Uvažujme nyní vrchol~$v$ na konci $(i+1)$-ní fáze a nějaký nejkratší $uv$-sled~$P$
o~$i+1$ hranách. Označme $wv$ poslední hranu tohoto sledu a $P'$ sled bez této hrany,
který tedy má délku~$i$. Podle indukčního předpokladu je na konci $i$-té fáze
$h(w)\le \ell(P')$. Tuto hodnotu získalo $h(w)$ nejpozději v~$i$-té fázi, při tom jsme
vrchol~$w$ otevřeli, takže jsme ho nejpozději v~$(i+1)$-ní fázi zavřeli a relaxovali.
Po této relaxaci je ovšem $h(v)\le h(w)+\ell(w,v)\le \ell(P') + \ell(w,v) = \ell(P)$.
\qed

\s{Cvičení:}
\itemize\ibull
\:Ukažte, že asymptoticky stejné časové složitosti by dosáhl algoritmus,
  který by vrcholy očísloval $v_1,\ldots,v_n$ a opakovaně by je v~tomto
  pořadí relaxoval tak dlouho, dokud by se ohodnocení měnila.
\:Jak algoritmus upravit, aby v~$i$-té fázi spočítal minimální délky sledů
  o~právě~$i$ hranách?
\:Jak lze algoritmus BFM využít k~nalezení záporného cyklu?
\endlist

\h{Dijkstrův algoritmus}

Pokud jsou všechny délky hran nezáporné, můžeme použít efektivnější pravidlo
pro výběr vrcholu navržené Dijkstrou \cite{dijkstra:mstandpath}. To říká, že vždy relaxujeme ten z~otevřených
vrcholů, jehož ohodnocení je nejmenší.

\s{Věta:} Dijkstrův algoritmus uzavírá vrcholy v~pořadí podle neklesající
vzdálenosti od~$u$ a každý dosažitelný vrchol uzavře právě jednou.

\proof
Indukcí dokážeme, že v~každém okamžiku mají všechny uzavřené vrcholy ohodnocení
menší nebo rovné ohodnocením všech otevřených vrcholů. Na~počátku to jistě platí.
Nechť nyní uzavíráme vrchol~$v$ s~minimálním $h(v)$ mezi otevřenými. Během jeho
relaxace nemůžeme žádnou hodnotu snížit pod~$h(v)$, jelikož v~grafu s~nezápornými
hranami je $h(v) + \ell(v,w) \ge h(v)$. Hodnota zbývajících otevřených vrcholů
tedy neklesne pod hodnotu tohoto nově uzavřeného. Hodnoty dříve uzavřených vrcholů
se nemohou nijak změnit.
\qed

Přímočará implementace Dijkstrova algoritmu by tedy pokaždé v~čase $\O(n)$
vybrala otevřený vrchol s~nejmenším ohodnocením, v~čase $\O(n)$ ho relaxovala
a toto by se opakovalo nejvýše $n$-krát. Algoritmus by tudíž doběhl v~čase $\O(n^2)$,
což je pro husté grafy zajisté optimální. Zkusíme nyní zrychlit výpočet
na~řídkých grafech.

Všechny relaxace trvají dohromady $\O(\sum_v \deg(v)) = \O(m)$, takže úzkým hrdlem je
vybírání minima. Použijeme pro něj vhodnou datovou strukturu, v~níž budeme udržovat
množinu všech otevřených vrcholů spolu s~jejich ohodnoceními. Od~datové struktury
potřebujeme, aby uměla operace \<Insert> (vložení vrcholu), \<ExtractMin> (nalezení
a smazání minima) a \<Decrease> (snížení hodnoty vrcholu). První dvě operace přitom
voláme nejvýše $n$-krát a operaci \<Decrease> nejvýše $m$-krát. Celý algoritmus
tedy doběhne v~čase
$$\O(nT_I(n) + nT_E(n) + mT_D(n)),$$
kde $T_I(n)$, $T_E(n)$ a $T_D(n)$ jsou časové složitosti jednotlivých operací
na~struktuře o~nejvýše~$n$ prvcích (stačí amortizovaně).

\>Jaké možnosti máme pro volbu struktury?

\itemize\ibull
\:{\I pole} -- \<Insert> a \<Decrease> stojí konstantu, \<ExtractMin> trvá $\O(n)$,
  celkem tedy $\O(n^2)$.
\:{\I (binární) halda} -- všechny tři operace umíme provést v~čase $\O(\log n)$, takže celkem
  $\O(m\log n)$. To je pro husté grafy horší, pro řídké lepší.
\:{\I $k$-regulární halda} -- pokud haldu upravíme tak, že každý prvek bude mít až $k$ synů,
  hloubka haldy klesne na~$\O(\log_k n)$. Operace \uv{vybublávající} prvky směrem nahoru,
  což je \<Insert> a \<Decrease>, se zrychlí na~$\O(\log_k n)$. Ovšem \<ExtractMin> potřebuje
  zkoumat všechny syny každého navštíveného prvku, takže se zpomalí na $\O(k\log_k n)$.

  Celková složitost tedy vyjde $\O(nk\log_k n + m\log_k n)$. Oba členy se vyrovnají
  pro $k=m/n$, čímž získáme $\O(m\log_{m/n} n)$. Člen $\log_{m/n} n$ je přitom $\O(1)$,
  kdykoliv je $m\ge n^{1+\varepsilon}$ pro nějaké~$\varepsilon>0$, takže pro dostatečně
  husté grafy jsme získali lineární algoritmus.

  (Všimněte si, že pro $m\approx n^2$ algoritmus zvolí $k\approx n$, takže halda degeneruje
  na jediné patro, tedy na pole, které se opravdu ukázalo být optimální volbou pro husté grafy.)
\:{\I Fibonacciho halda} \cite{ft:fibonacci} -- \<Insert> a \<Decrease> stojí $\O(1)$, \<ExtractMin> má složitost
  $\O(\log n)$ [vše amortizovaně]. Dijkstrův algoritmus proto doběhne v~čase $\O(m + n\log n)$.
  To je lineární pro grafy s~hustotou $\Omega(\log n)$. Téže složitosti operací dosahují
  i jiné, méně známé haldy \cite{haeupler:rankph,elmasry:violheap}, které mohou být v~praxi
  výrazně rychlejší.
\:{\I Monotónní haldy} -- můžeme použít nějakou jinou haldu, která využívá toho,
  že posloupnost odebíraných prvků je neklesající. Pro celá čísla na~\hbox{RAMu} to může
  být například Thorupova halda \cite{thorup:queue} se složitostí $\O(\log\log n)$ u~operace \<ExtractMin>
  a $\O(1)$ u~ostatních operací. Dijkstra tedy běží v~$\O(m + n\log\log n)$.
\:{\I Datové struktury pro omezené universum} -- prozkoumáme vzápětí.
\endlist

\s{Cvičení:}

\itemize\ibull
\:Najděte příklad grafu se zápornými hranami (ale bez záporných cyklů),
  na~kterém Dijkstrův algoritmus selže.
\:Rozmyslete si, že pokud nevyužijeme nějaké speciální vlastnosti čísel (celočíselnost,
  omezený rozsah), je mez $\O(m+n\log n)$ nejlepší možná, protože Dijkstrovým algoritmem
  můžeme třídit $n$-tici čísel. Thorup dokonce dokázal \cite{thorup:equiv}, že z~každého třídícího algoritmu
  se složitostí $\O(nT(n))$ můžeme odvodit haldu se složitostí mazání $\O(T(n))$.
\:Jsou-li délky hran celočíselné, můžeme se na Dijkstrův algoritmus dívat i takto:
  Představme si, že každou hranu nahradíme cestou tvořenou příslušným počtem hran jednotkové délky
  a na vzniklý neohodnocený graf spustíme prohledávání do~šířky. To samozřejmě vydá
  správný výsledek, ale poměrně pomalu, protože bude většinu času trávit posouváním
  vlny \uv{uvnitř} původních hran. Můžeme si tedy pro každou původní hranu nařídit
  \uv{budík}, který nám řekne, za~kolik posunutí vlny dospějeme na~její konec.
  Dokažte, že tento algoritmus je ekvivalentní s~Dijkstrovým.
\endlist

\h{Celočíselné délky}

Uvažujme nyní grafy, v~nichž jsou všechny délky hran nezáporná celá čísla omezená
nějakou konstantou~$L$. Všechny vzdálenosti jsou tedy omezeny číslem~$nL$, takže
nám stačí datová struktura schopná uchovávat takto omezená celá čísla.

Použijeme jednoduchou přihrádkovou strukturu: pole indexované hodnotami od~0 do~$nL$,
jeho $i$-tý prvek bude obsahovat seznam vrcholů, jejichž ohodnocení je rovno~$i$.
Operace \<Insert> a \<Decrease> zvládneme v~konstantním čase, budeme-li si u~každého
prvku pamatovat jeho polohu v~seznamu. Operace \<ExtractMin> potřebuje najít první
neprázdnou přihrádku, ale jelikož víme, že posloupnost odebíraných minim je monotónní,
stačí hledat od místa, kde se hledání zastavilo minule. Všechna hledání přihrádek
tedy zaberou dohromady $\O(nL)$ a celý Dijkstrův algoritmus bude trvat $\O(nL + m)$.

Prostorová složitost $\O(nL+m)$ je nevalná, ale můžeme ji jednoduchým trikem
snížit: Všimneme si, že všechna konečná ohodnocení vrcholů nemohou být větší
než aktuální minimum zvětšené o~$L$. Jinými slovy všechny neprázdné přihrádky
se nacházejí v~úseku pole dlouhém~$L+1$, takže stačí indexovat modulo~$L+1$.
Pouze si musíme dávat pozor, abychom správně poznali, kdy se struktura
vyprázdnila, což zjistíme například pomocí počítadla otevřených vrcholů. Čas si
asymptoticky nezhoršíme, prostor klesne na~$\O(L+m)$.

Podobný trik můžeme použít i pro libovolnou jinou datovou strukturu: rozsah čísel
rozdělíme na~\uv{okna} velikosti~$L$ (v~$i$-tém okně jsou čísla $iL,iL+1,\ldots,(i+1)L-1$).
V~libovolné chvíli mohou tedy být neprázdná nejvýše dvě okna. Stačí nám proto
pořídit si dvě struktury pro ukládání čísel v~rozsahu $0,\ldots,L-1$ -- jedna
z~nich bude reprezentovat aktuální okno (to, v~němž leželo minulé minimum),
druhá okno bezprostředně následující. Minimum mažeme z~první struktury; pokud
už je prázdná, obě struktury prohodíme. Operace \<Insert> podle hodnoty určí,
do~které struktury se má vkládat. S~operací \<Decrease> je to složitější --
hodnota z~vyšší struktury může přeskočit do té nižší, ale v~takovém případě
ji ve~vyšší struktuře vymažeme (to je \<Decrease> na $-\infty$ následovaný
\<ExtractMin>em) a do~té nižší vložíme. To se každému prvku může přihodit nejvýše
jednou, takže stále platí, že se každý prvek účastní $\O(1)$ vložení a $\O(1)$
extrakcí minima.

Ukázali jsme tedy, že pro naše potřeby postačuje struktura schopná uchovávání
čísel menších nebo rovných~$L$.

Nabízí se použít van Emde-Boasův strom z~kapitoly o~výpočetních modelech.
Ten dosahuje složitosti $\O(\log\log L)$ pro operace \<Insert> a \<ExtractMin>,
operaci \<Decrease> musíme překládat na \<Delete> a \<Insert>. Celková
složitost Dijkstrova algoritmu vyjde $\O(L+m\log\log L)$, přičemž čas~$L$
spotřebujeme na inicializaci struktury (té se lze za jistých podmínek vyhnout,
viz zmíněná kapitola).

Vraťme se ale ještě k~využití přihrádek\dots

\h{Víceúrovňové přihrádky}

Podobně jako u~třídění čísel, i~zde se vyplácí stavět přihrádkové struktury
víceúrovňově (původně popsáno Goldbergem a Silversteinem \cite{goldberg:mlb}).
Jednotlivé hodnoty budeme zapisovat v~soustavě o~základu~$B$,
který zvolíme jako nějakou mocninu dvojky, abychom mohli s~číslicemi tohoto
zápisu snadno zacházet pomocí bitových operací. Každé číslo tedy zabere nejvýše
$d=1+\lfloor\log_B L\rfloor$ číslic; pokud bude kratší, doplníme ho zleva nulami.

Nejvyšší patro struktury bude tvořeno polem $B$~přihrádek, v~$i$-té z~nich
budou uložena ta čísla, jejichž číslice nejvyššího řádu je rovna~$i$. Za~{\I aktivní}
prohlásíme tu přihrádku, která obsahuje aktuální minimum. Přihrádky s~menšími
indexy jsou prázdné a zůstanou takové až do~konce výpočtu, protože halda
je monotónní. Pokud v~přihrádce obsahující minimum bude více prvků, budeme
ji rozkládat podle druhého nejvyššího řádu na dalších~$B$ přihrádek atd.
Celkem tak vznikne až~$d$ úrovní.

\>Struktura bude obsahovat následující data:

\itemize\ibull
\:Parametry $L$, $B$ a~$d$.
\:Pole úrovní (nejvyšší má číslo~$d-1$, nejnižší~0), každá úroveň je buďto prázdná
  (a pak jsou prázdné i~všechny nižší), nebo obsahuje pole~$U_i$ o~$B$ přihrádkách
  a v~každé z~nich seznam prvků. Pole úrovní používáme jako zásobník, udržujeme
  si číslo nejnižší neprázdné úrovně.
\:Hodnotu~$\mu$ předchozího odebraného minima.
\endlist

Operace \<Insert> vloží hodnotu do~nejhlubší možné přihrádky. Podívá se tedy
na~nejvyšší úroveň: pokud hodnota patří do přihrádky, která není aktivní, vloží
ji přímo. Jinak přejde o~úroveň níže a zopakuje stejný postup. To vše lze provést
v~konstantním čase: stačí se podívat, jaký je nejvyšší jedničkový bit ve~{\sc xor}u
nové hodnoty s~číslem~$\mu$ (opět viz kapitola o~výpočetních modelech), a tím zjistit
číslo úrovně, kam hodnota patří.

Pokud chceme provést \<Decrease>, odstraníme hodnotu z~přihrádky, ve~které se
právě nachází (polohu si můžeme u~každé hodnoty pamatovat zvlášť), a znovu ji
vložíme.

Většinu práce samozřejmě přenecháme funkci \<ExtractMin>. Ta začne prohledávat
nejnižší obsazenou úroveň od~aktivní přihrádky dál (to, která přihrádka je na
které úrovni aktivní, poznáme z~číslic hodnoty~$\mu$). Pokud přihrádky na~této
úrovni dojdou, prázdnou úroveň zrušíme a pokračujeme o~patro výše.

Jakmile najdeme neprázdnou přihrádku, nalezneme v~ní minimum a to se stane novým~$\mu$.
Pokud v~přihrádce nebyly žádné další prvky, skončíme. V~opačném případě zbývající
prvky rozprostřeme do~přihrádek na~bezprostředně nižší úrovni, kterou tím založíme.

Čas strávený hledáním minima můžeme rozdělit na~několik částí:

\itemize\ibull
\:$\O(B)$ na inicializaci nové úrovně -- to naúčtujeme prvku, který jsme
  právě mazali;
\:hledání neprázdných přihrádek -- prozkoumání každé prázdné přihrádky
  naúčtujeme jejímu vytvoření, což se rozpustí v~$\O(B)$ na inicializaci
  úrovně;
\:zrušení úrovně -- opět naúčtujeme jejímu vzniku;
\:rozhazování prvků do přihrádek -- jelikož prvky v~hierarchii přihrádek
  putují během operací pouze doleva a dolů (jejich hodnoty se nikdy nezvětšují),
  klesne každý prvek nejvýše~$d$-krát, takže stačí, když na všechna rozhazování
  přispěje časem $\O(d)$;
\:hledání minima -- minimum naúčtujeme smazanému prvku, ostatní prvky,
  které jsme museli projít, naúčtujeme jejich rozhazování.
\endlist

\>Stačí tedy, aby každý prvek při \<Insert>u zaplatil čas $\O(B+d)$ a jak \<Decrease>,
tak \<ExtractMin> budou mít konstantní amortizovanou složitost. Dijkstrův
algoritmus pak poběží v~$\O(m + n(B+d))$.

Zbývá nastavit parametry tak, abychom minimalizovali výraz $B+d = B + \log L/\log B$.
Vhodná volba je $B=\log L/\log\log L$. Při ní platí
$$
{\log L\over\log B} = {\log L \over \log\left(\log L/\log\log L\right) }
= {\log L\over \log\log L - \log\log\log L} = \Theta(B).
$$
Tehdy Dijkstra vydá výsledek v~čase $\O(m + n\cdot{\log L\over\log\log L})$.

\h{HOT Queue -- kombinace přihrádek s~haldou}

Cherkassky, Goldberg a Silverstein \cite{cherkassky:hotq} si všimli, že ve~víceúrovňových přihrádkových strukturách
platíme příliš mnoho za~úrovně, ve~kterých se za~dobu jejich existence objeví jen malé
množství prvků. Navrhli tedy ukládat prvky z~\uv{malých} úrovní do~společné haldy.
Výsledné struktuře se říká HOT (Heap-on-Top) Queue. My si předvedeme její upravenou
variantu (v~té původní se skrývá několik chyb).

Pořídíme si haldu, řekněme Fibonacciho, a~navíc ke~každé úrovni počítadlo udávající,
kolik prvků z~této úrovně jsme uložili do~haldy. Dokud toto počítadlo nepřeroste nějaký
parametr~$H$, přihrádky nebudeme zakládat a prvky poputují do~haldy. Čas $\O(B)$ na
založení úrovně a její procházení proto můžeme rozpočítat mezi~$H$ prvků, které se musely
na~dané úrovni objevit, než byla rozpřihrádkována. (Povšimněte si, že počítadlo nikdy
nesnižujeme, pouze ho vynulujeme, když je úroveň zrušena. Proto vůbec nemusí odpovídat
skutečnému počtu prvků z~příslušné úrovně, které jsou právě uloženy v~haldě. To ovšem
vůbec nevadí -- počítadlo pouze hlídá, aby se úroveň nevytvořila příliš brzy, tedy abychom
měli dost prvků k~rozúčtování času.)

Proměnnou~$\mu$ necháme ukazovat na~místo, kde jsme se při hledání minima v~přihrádkách
zastavili. Současné globální minimum struktury může být nižší, nachází-li se minimum
zrovna v~haldě. Stále je však zaručeno, že před~$\mu$ se nenachází žádná
neprázdná přihrádka.

Operace budou fungovat takto:

\>\<Insert>:
\algo
\:Spočítáme, do~které úrovně~$i$ má prvek padnout (bitovými operacemi).
\:Pokud je počítadlo této úrovně menší než~$H$, zvýšíme ho, vložíme prvek do~haldy a skočíme.
\:Nebyly-li ještě pro tuto úroveň založeny přihrádky, vyrobíme prázdné.
\:Vložíme prvek do~příslušné přihrádky.
\endalgo

\>\<Decrease>:
\algo
\:Pokud se prvek nachází v~haldě (to si u~každého prvku pamatujeme), provedeme
  \<Decrease> v~haldě a skončíme.
\:Smažeme prvek z~jeho přihrádky a provedeme \<Insert> s~novou hodnotou.
\endalgo

\>\<ExtractMin>:
\algo
\:Dokud je~$\mu$ menší než aktuální minimum haldy, opakujeme:
\::Najdeme přihrádku odpovídající hodnotě~$\mu$.
\::Je-li tato přihrádka prázdná, přejdeme na~další (upravíme~$\mu$). Jsme-li na konci úrovně,
   zrušíme ji, vynulujeme její počítadlo a pokračujeme o~úroveň výš.
\::Není-li prázdná, rozprostřeme ji o~úroveň níž (stejným způsobem jako při \<Insert>u,
   takže prvních~$H$ prvků vložíme do~haldy).
\:Smažeme minimum z~haldy a vrátíme ho jako výsledek.
\endalgo

\>Pustíme se do~analýzy složitosti. Jako parametry si zvolíme počet hladin~$d$ (takže
počet přihrádek~$B$ na jedné úrovni je roven $L^{1/d}$) a \uv{haldovou konstantu}~$H$.

Nejprve si všimneme, že než počítadlo nějaké úrovně vynulujeme, jsou bezpečně
z~haldy pryč všechny prvky patřící do~této úrovně. Celkem se tedy v~haldě
vyskytuje nejvýše $\O(dH)$ prvků. \<ExtractMin> v~haldě proto trvá $\O(\log(dH))$,
ostatní haldové operace $\O(1)$.

Nyní rozúčtujeme čas operací mezi jednotlivé prvky (opět si vše předplatíme
v~\<Insert>u a ostatní operace poběží v~amortizovaně konstantním čase):

\itemize\ibull
\:Každý prvek může být nejvýše jednou za~dobu svého života vložen do~haldy
  a nejvýše jednou z~ní vyjmut. Na~obojí dohromady přispěje $\O(\log dH)$.
\:Prvek se účastní nejvýše~$d$ přehození do~nižší úrovně. Pokud byl přihozen
  do~haldy, už tam setrvá, jinak pokaždé zaplatí $\O(1)$ za~zařazení do~přihrádky,
  celkem tedy $\O(d)$ na prvek.
\:Vytvoření, projití a smazání přihrádek na~jedné úrovni nastane až tehdy, co bylo
  $H$~prvků patřících do~této úrovně vloženo do~haldy. Stačí tedy, aby každý
  prvek přispěl časem $\O(B/H) = \O(L^{1/d}/H)$.
\endlist

\>Každý prvek tedy platí $\O(d + \log dH + L^{1/d}/H) = \O(d + \log H + L^{1/d}/H)$.
Pojďme najít nastavení parametrů, které tento výraz minimalizuje.
Nejprve zvolme~$H$ tak, aby se~$d$ vyrovnalo s~$L^{1/d}/H$. Tedy $H = L^{1/d}/d$.
Celý výraz tím zjednodušíme na $\O(d + \log\,(L^{1/d}/d))$ =
$\O(d + 1/d\cdot\log L - \log d) = \O(d + 1/d\cdot\log L)$. Oba sčítance volbou
$d=\sqrt{\log L}$ vyrovnáme.

HOT Queue tedy zvládne \<Insert> s~amortizovanou časovou složitostí $\O(\sqrt{\log L})$
a ostatní operace v~čase amortizovaně konstantním. Použijeme-li tuto strukturu
v~Dijkstrově algoritmu, spočte vzdálenosti v~čase $\O(m + n\sqrt{\log L})$.

\h{Dinicův algoritmus}

Zajímavé vylepšení Dijkstrova algoritmu navrhl Dinic. Všiml si, že pokud
je každá hrana dlouhá alespoň~$\delta$, můžeme uzavírat nejen
vrchol s~minimálním ohodnocením~$\mu$, ale i všechny s~ohodnocením
menším než $\mu+\delta$.

Pro takto upravený Dijkstrův algoritmus bude stále platit, že při uzavírání
vrcholu odpovídá ohodnocení skutečné vzdálenosti, takže uzavřené vrcholy již
nejsou znovu otevírány.

O~monotonii vzdáleností jsme sice přišli, ale v~přihrádkové struktuře nebo
haldě můžeme klíče nahradit hodnotami $h'(v) := \lfloor h(v)/\delta \rfloor$.
Tyto hodnoty se totiž chovají monotónně a vrcholy se stejným $h'(v)$ můžeme
libovolně zaměňovat.

Kteroukoli z~popsaných přihrádkových struktur můžeme tedy použít, pouze
v~rozboru časové složitosti nahradíme~$L$ výrazem $L/\delta$. Tento přístup
přitom funguje i pro neceločíselné délky hran, pouze potřebujeme mít předem
k~dispozici netriviální dolní odhad na~všechny délky.

\h{Potenciály}

Viděli jsme, že v~grafech s~nezápornými délkami hran se nejkratší cesty
hledají snáze. Nabízí se nalézt nějakou transformaci, která by
dovedla délky hran upravit tak, aby byly nejkratší cesty zachovány (samozřejmě
ne jejich délky, ale alespoň to, které cesty jsou nejkratší). Nabízí se
následující fyzikální inspirace:

\s{Definice:} {\I Potenciál} budeme říkat libovolné funkci $\psi: V\rightarrow {\bb R}$.
Pro každý potenciál zavedeme {\I redukované délky hran} $\ell_\psi(u,v) := \ell(u,v) + \psi(u) - \psi(v)$.
Potenciál nazveme {\I přípustný,} pokud žádná hrana nemá zápornou redukovanou délku.

\s{Pozorování:} Pro redukovanou délku libovolné cesty~$P$ z~$u$ do~$v$ platí: $\ell_\psi(P) = \ell(P) + \psi(u) - \psi(v)$.

\proof
Nechť cesta~$P$ prochází přes vrcholy $u=w_1,\ldots,w_k=v$. Potom:
$$
\ell_\psi(P) = \sum_i \ell_\psi(w_i,w_{i+1}) = \sum_i \left( \ell(w_i,w_{i+1}) + \psi(w_i) - \psi(w_{i+1}) \right).
$$
Tato suma je ovšem teleskopická, takže z~ní zbude
$$
\sum_i\ell(w_i,w_{i+1}) + \psi(w_1) - \psi(w_k) = \ell(P) + \psi(u) - \psi(v).
$$
\vskip-\baselineskip
\qed

\s{Důsledek:} Potenciálovou redukcí se délky všech cest mezi~$u$ a~$v$
změní o~tutéž konstantu, takže struktura nejkratších cest zůstane nezměněna.

Zbývá přijít na~to, kde si obstarat nějaký přípustný potenciál. Přidejme do~grafu
nový vrchol~$z$, přiveďme z~něj hrany nulové délky do~všech ostatních vrcholů
a~označme~$\psi(v)$ vzdálenost ze~$z$ do~$v$ v~tomto grafu. Aby byl tento potenciál
přípustný, musí pro každou hranu $uv$ platit $\ell_\psi(u,v) = \ell(u,v) + \psi(u) - \psi(v) \ge 0$.
Tuto nerovnost můžeme upravit na $\ell(u,v) + d(z,u) - d(z,v) \ge 0$, čili
$d(z,u) + \ell(u,v) \ge d(z,v)$, což je ale obyčejná trojúhelníková nerovnost
pro vzdálenost v~grafu, která jistě platí.

Jedním výpočtem nejkratších cest v~grafu se zápornými hranami (třeba algoritmem BFM)
tedy dokážeme spočítat potenciál, který nám poslouží k~redukci všech hran na~nezáporné
délky. To nám samozřejmě nepomůže, chceme-li jednorázově hledat nejkratší cestu,
ale může nám to výrazně zjednodušit další, složitější práci s~grafem. Jak uvidíme
v~příští kapitole, můžeme tak například nalézt vzdálenosti mezi všemi dvojicemi
vrcholů v~čase $\O(nm + n^2\log n)$.

Na~závěr tohoto oddílu dokážeme jedno pomocné tvrzení o~potenciálech, které
nám pomůže v~konstrukci algoritmů typu \ppsp:

\s{Lemma:} Pokud $f$ a~$g$ jsou přípustné potenciály, pak jsou jimi i:
\numlist\ndotted
\:konvexní kombinace $f$ a~$g$, tedy $\alpha f + \beta g$ pro libovolné $\alpha,\beta\ge 0, \alpha+\beta=1$;
\:$\min(f,g)$;
\:$\max(f,g)$.
\endlist

\proof Buď $uv$ hrana. Potom z~definice přípustnosti platí $\ell(u,v) \ge f(v) - f(u)$ a $\ell(u,v) \ge g(v) - g(u)$.
Jednotlivé části tvrzení dokážeme takto:
\numlist\ndotted
\:Pokud obě strany nerovnosti pro~$f$ vynásobíme konstantou~$\alpha$, u~nerovnosti pro~$g$
  konstantou~$\beta$ a obě nerovnosti sečteme, dostaneme:
  $$
  (\alpha+\beta) \cdot \ell(u,v) \ge (\alpha f(v) + \beta g(v)) - (\alpha f(u) + \beta g(u)),
  $$
  což je přesně požadovaná nerovnost pro přípustnost funkce $\alpha f+\beta g$.
\:Označme $h := \min(f,g)$. Nechť bez újmy na obecnosti $f(u)\le g(u)$. Pokud také platí $f(v)\le g(v)$,
  shoduje se minimum s~funkcí~$f$ a není co dokazovat. V~opačném případě je $h(u) = f(u)$, $h(v) = g(v)$.
  Tehdy si stačí všimnout, že $h(v) - h(u) = g(v) - f(u) < f(v) - f(u) \le \ell(u,v)$, takže
  potenciál~$h$ je přípustný.
\:Dokážeme analogicky.
\qeditem
\endlist

\h{Algoritmy pro problém typu \ppsp}

Zaměřme se nyní na~případ, kdy chceme hledat nejkratší cesty mezi zadanou dvojicí
vrcholů $s$,~$t$. Obvykle se i v~této situaci používají algoritmy \sssp{} (SSSP) a v~obecném
případě ani není efektivnější řešení známo. Existuje ovšem velké množství heuristik, kterými
lze obvykle výpočet zrychlit. Některé z~nich si předvedeme na Dijkstrově algoritmu.

Dijkstrův algoritmus ve~své klasické podobě neví vůbec nic o~cílovém vrcholu a
prohledá celý graf. Hned se nabízí využít toho, že od~okamžiku uzavření
kteréhokoliv vrcholu se již jeho ohodnocení nezmění. Pokud tedy uzavřeme cílový
vrchol, můžeme se zastavit.

Jakou část grafu prohledáváme teď? V~metrice dané vzdálenostmi v~grafu je to nejmenší
koule se středem ve~vrcholu~$u$, která obsahuje nejkratší cestu (dobře se to
představuje na~hledání v~silniční síti na~rovinné mapě).

Také můžeme spustit prohledávání z~obou konců zároveň, tedy zkombinovat hledání
od~$s$ v~původním grafu s~hledáním od~$t$ v~grafu s~obrácenou orientací hran.
Oba postupy můžeme libovolně střídat a zastavíme se v~okamžiku, kdy jsme jeden
vrchol uzavřeli v~obou směrech. Pozor ovšem na to, že součet obou ohodnocení
tohoto vrcholu nemusí být roven $d(v,u)$ -- zkuste vymyslet protipříklad.
Nejkratší cesta ještě může vypadat tak, že přechází po nějaké hraně mezi vrcholem
uzavřeným v~jednom směru a vrcholem uzavřeným ve~směru druhém (ponechme bez důkazu).
Stačí tedy během relaxace zjistit, zda je konec hrany uzavřený v~opačném
směru prohledávání, a~pokud ano, započítat cestu do~průběžného minima.

Obousměrný Dijkstrův algoritmus projde sjednocení nějaké koule okolo~$s$ s~nějakou
koulí okolo~$t$, které obsahuje nejkratší cestu. Průměry koulí přitom závisí na tom,
jak budeme během výpočtu střídat oba směry prohledávání. V~nejhorším případě samozřejmě
můžeme prohledat celý graf.

\h{Algoritmus \astar}

V~umělé inteligenci se často pro hledání nejkratší cesty v~rozsáhlých grafech
(obvykle stavových prostorech úloh) používá algoritmus nazývaný~\astar{} \cite{hart:astar}.
Jedná se o~modifikaci Dijkstrova algoritmu, která využívá heuristickou funkci
pro dolní odhad vzdálenosti do~cíle; označme si ji $\psi(v)$. V~každém kroku pak uzavíra
vrchol~$v$ s~nejmenším možným součtem $h(v)+\psi(v)$ aktuálního ohodnocení s~heuristikou.

Intuice za tímto algoritmem je jasná: pokud víme, že nějaký vrchol je blízko
od~počátačního vrcholu~$s$, ale bude z~něj určitě daleko do cíle~$t$, zatím ho
odložíme a budeme zkoumat nadějnější varianty.

Heuristika se přitom volí podle konkrétního problému -- např. hledáme-li cestu
v~mapě, můžeme použít vzdálenost do~cíle vzdušnou čarou.

Je u~tohoto algoritmu zaručeno, že vždy najde nejkratší cestu? Na to nám dá odpověď
teorie potenciálů:

\s{Věta:} Běh algoritmu \astar{} odpovídá průběhu Dijkstrova algoritmu
na~grafu redukovaném potenciálem~$-\psi$. Přesněji,
pokud označíme $h^*$ aktuální ohodnocení v~\astar{} a $h$ aktuální ohodnocení
v~synchronně běžícím Dijkstrovi, bude vždy platit $h(v) = h^*(v) - \psi(s) + \psi(v)$.

\proof
Indukcí podle doby běhu obou algoritmů. Na počátku je $h^*(s)$ i $h(s)$ nulové
a všechna ostatní $h^*$ a~$h$ jsou nekonečná, takže tvrzení platí. V~každém dalším
kroku \astar{} vybere vrchol~$v$ s~nejmenším $h^*(v) + \psi(v)$, což je tentýž vrchol,
který vybere Dijkstra ($\psi(s)$ je stále stejné).

Uvažujme, co se stane během relaxace hrany $vw$: Dijkstra se pokusí snížit ohodnocení $h(w)$
o~$\delta = h(w) - h(v) - \ell_{-\psi}(v,w)$ a provede to, pokud $\delta>0$. Ukážeme,
že \astar{} udělá totéž:
$$\eqalign{
\delta &= (h^*(w) - \psi(s) + \psi(w)) - (h^*(v) - \psi(s) + \psi(v)) - (\ell(v,w) - \psi(v) + \psi(w)) \cr
&= h^*(w) - \psi(s) + \psi(w) - h^*(v) + \psi(s) - \psi(v) - \ell(v,w) + \psi(v) - \psi(w) \cr
&= h^*(w) - h^*(v) - \ell(v,w).
}$$
Oba algoritmy tedy až na~posunutí dané potenciálem počítají totéž.
\qed

\s{Důsledek:} Algoritmus \astar{} funguje jen tehdy, je-li potenciál $-\psi$ přípustný.

Například pro rovinnou mapu to heuristika daná euklidovskou vzdáleností~$\varrho$, tedy $\psi(v) := \varrho(v,t)$, splňuje:
Přípustnost požaduje pro každou hranu $uv$ nerovnost
$\ell(u,v) - \psi(v) + \psi(u) \ge 0$,
tedy $\ell(u,v) - \varrho(v,t) + \varrho(u,t) \ge 0$.
Jelikož $\ell(u,v) \ge \varrho(u,v)$,
stačí dokázat, že $\varrho(u,v) - \varrho(v,t) + \varrho(u,t) \ge 0$,
což je ovšem trojúhelníková nerovnost pro metriku~$\varrho$.

\references
\bye
