\input ../lecnotes.tex

\prednaska{6}{Dijkstrùv algoritmus a haldy}{}

{\bf FIXME: Nerevidováno!}

Na~této pøedná¹ce budeme pokraèovat v~problému hledání nejkrat¹ích cest
v~grafech ohodnocených reálnými èísly. Ji¾ jsme potkali Bellmanùv-Fordùv
algoritmus a jeho zobecnìní v~podobì prùzkumnického algoritmu.

\s{Situace:} Máme orientovany graf~$G$ a funkce $l : E(G) \rightarrow {\bb R}$
pøiøazující hranám jejich ohodnocení (délky). Pro vrcholy $u,v\in V(G)$ budeme
chtít spoèítat jejich vzdálenost $d(u,v)$, co¾ bude délka nejkrat¹í cesty z~$u$
do~$v$ nebo $\infty$, pokud ¾ádná cesta neexistuje.

Aby se vzdálenosti chovaly \uv{rozumnì} (tj. jako metrika), budeme chtít, aby platily
následující vlastnosti:

\itemize\ibull
\:$d(u, u) = 0$,
\:$d(u, v) \leq d(u, w) + d(w, v)$ (trojúhelníková nerovnost).
\endlist

To nemusí obecnì platit (kazí nám to záporné cykly), proto budeme studovat
pouze grafy, v~nich¾ záporné cykly neexistují. Pak u¾ budou obì vlastnosti
splnìny, jak plyne napøíklad z~následujícího lemmatu:

\s{Lemma:}
V~grafu bez záporných cyklù existuje ke~ka¾dému nejkrat¹ímu sledu z~$u$ do~$v$ stejnì dlouhá $uv$-cesta.

\proof
Máme-li nejkrat¹í $uv$-sled, který není cestou, opakuje se v~nìm nìjaký vrchol $w \in V(G)$.
Délka cyklu  $l(c) \geq  0 \Rightarrow l(u\dots v\dots w) \leq l(pùvodní sled)$. Tento postup mù¾eme opakovat a po koneèném poètu krokù dostaneme cestu, tedy platí trojúhelníková nerovnost.
\qed

Opakování: Dijkstrùv algoritmus
\itemize\ibull
\:$D(v)$ \dots doèasná vzdálenost z $s$ do $v$
\:Znaèky $Z(v)$ \itemize\ibull
\::Nevidìn
\::Vidìn
\::Hotov
\endlist
\endlist

%druha strana zapisku
\algo
\:$D(*) \leftarrow +\infty , D(s) \leftarrow 0$
\:$Z(*) \leftarrow Neviden, Z(s) \leftarrow V$
\:while $\exists v : Z(v) = V$
\::vybereme $v : Z(v) = V, D(v) = min$
\::$Z(v) = H$
\::for $\forall w : (v, w) \in E(G)$
\:::$D(w) \leftarrow min( D(w), D(w) + l(v, w))$
\::if $Z(w) = N \Rightarrow Z(w) \leftarrow V$
\endalgo

\s{Vìta:} Pokud $G$ je nezápornì ohodnocený graf, pak se Dijkstrùv algoritmus zastaví a vydá $\forall v : D(v) = d(s, v)$ (tedy správné hodnoty).

\proof Následující posloupností lemmat.\qed

\s{Lemma 1:} Pokud $v_0,\dots,v_k$ je nejkrat¹í $v_0v_k$-cesta, pak $v_0,\dots,v_{k-1}$ je nejkrat¹í $v_0v_{k-1}$-cesta.

\proof
Pokud by tomu tak nebylo, mù¾eme $v_0,\dots,v_{k-1}$ vymìnit za~krat¹í cestu, a~tím
získat krat¹í $v_0v_k$-cestu.
\qed

\s{Lemma 2:} Algoritmus se zastaví po $\leq n$ prùchodech cyklem.

\proof
Zøejmé z~toho, ¾e ka¾dý vrchol uzavøeme nejvý¹e jednou.
\qed

\s{Lemma 3:} Po zastavení jsou hotovy právì vrcholy dosa¾itelné z $s$.

\proof
Viz minulá pøedná¹ka.
\qed

\s{Lemma 4:} $D(v)$ uzavíraných vrcholù tvoøí neklesající posloupnost.

\proof
V okam¾iku, kdy uzavíráme $v$ platí $\forall w \notin H : D(w) \geq D(v)$, pøípadnì pøepoèítáme $D(w)$ na $D(v) - l(v, w) \geq D(v)$.
\qed

\s{Lemma 5:} Pokud $v \in H$, pak $D(v)$ se u¾ nezmìní.

\proof
Indukcí podle bìhu algoritmu.
\qed

\s{Lemma 6:} Pro $\forall v D(v)$ je délka nejkrat¹í $sv$-cesty, její¾ vnitøní vrcholy le¾í v¹echny v $H$.

\proof
\itemize\ibull
\:po 1. prùchodu OK
\:uzavíráme-li dal¹í vrchol $v$:
\itemize\relax
\:a) $D(w)$ pro $w \in H$
Podle Lemma 5 se $D(w)$ nemìní. Musíme nahlédnout, ¾e se opravdu zmìnit nemá.
\:b) $D(w)$ pro $w \notin H$
$D(w) = min{D(v) + l(v, w)}$
\endlist
\endlist
\qed

Existuje pomalej¹í algoritmus pro grafy se zápornými hranami bez záporných cyklù.
\s{Bellman-Fordùv algoritmus}
\algo
\:$D(*) \leftarrow \infty, D(s) \leftarrow 0$
\:Opakuji
\::Pro $\forall v \in V$
\:::$prozkoumej(v)$
\:::(koukne se, jestli nejde vylep¹it cestu¨
\:::do sousedù $v$)
\:dokud se nìjaké $D(\dots)$ mìní
\endalgo

\s{Lemma 1:} Pokud $D(v) < \infty$, pak existuje sled z $s$ do $v$ délky $D(v)$.
(speciálnì z toho plyne $\forall v D(v) \geq d(s,v)$)

\s{Lemma 2:} $\forall v D(v)$ nikdy neroste.
\s{Lemma 3:} Po $k$ fázích je $\forall v D(v) \leq$ délka nejkrat¹ího $sv$-sledu o $\leq k$ hranách.
%ctvrta stranka
\proof
Indukcí\dots pro $k \geq 0$ OK
Indukèní krok: Dobìhla $k-1$ fáze, pou¹tíme $k$-tou

\qed
\s{Vìta:} Pro graf bez záporných cyklù se Bellman-Fordùv algoritmus zastaví po nejvý¹e $m$ fázích a vydá $D(v) = d(s, v)$ pro v¹echna $v$. (zøejmé z lemmat)

\s{Lemma 4:} Pokud v grafu existuje záporný cyklus dosa¾itelný z $s$, algoritmus se nezastaví. (Zajímavý test na to, zda graf obsahuje záporný cyklus.)

Èasová slo¾itost Bellman-Fordova algoritmu : $O(n*m)$

\s{Floyd-Warshallùv algoritmus}
$G$ je graf se záporným ohodnocením hran, bez záporných cyklù
$D_{i,j}^k$ = délka nejkrat¹í cesty z $v_i$ do $v_j$ pøes $v_1 \dots v_k$
%pozorovani
$D_{ij}^0 = l(v_i, v_j)$, $D_{ii}^0 = 0$
$D_{ij}^n = d(v_i, v_j)$ - skuteèná vzdálenost v grafu
\algo
\:$D_{i,j} \rightarrow l(v_i, v_j), D_{i,i} \rightarrow 0 \forall i, j$
\:for $k = 1$ to n
\::for $i = 1$ to n
\:::for $j = 1$ to n
\::::$D_{i,j} = min(D_{i,j}, D_{i,k} + D_{k,j})$
\endalgo

\s{Vìta:} Floyd-Warshallùv algoritmus spoèítá $D_{i,j} = d(v_i, v_j)$ v èase $O(n^3)$.

\>Shrnutí:

\s{$s \rightarrow *$}
Dijkstrùv algoritmus $O(n^2)$
\dots s haldou $O((n+m)\log m)$
\dots s regulární haldou $O(n + m*log n)$
\dots s Fibbonaciho haldou $O(n*log n + m)$
Bellman-Ford $O(n*m)$

\s{$* \rightarrow *$}
Floyd-Warshall $O(n^3)$

\bye
