\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)$.
\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
