\input slidemac.tex

\language=\czech
\chyph

\def\note{\color{RawSienna}}
\def\cmt{~~\color{Blue}}
\def\?{\ifmmode\hbox{\bffont ?}\else{\sem ?}\fi}

\slide{Nejkrat¹í cesty: Prùzkumnický algoritmus}

$\<Hledej>(v_0):$

\algo
\:$Z(*)\leftarrow{\bf N}$, $Z(v_0)={\bf O}$ {\cmt znaèky: {\sem N}evidìn, {\sem O}tevøen, {\sem U}zavøen}
\:$D(*)\leftarrow\infty$, $D(v_0)=0$ {\cmt odhady vzdáleností}
\:$P(*)\leftarrow \?$ {\cmt pøedchùdci, \?=nedefinováno}
\:Dokud existuje vrchol~$u$ takový, ¾e $Z(u)={\bf O}$:
\::{\note Prozkoumáme vrchol~$u$, èili:}
\::$Z(u)\leftarrow{\bf U}$
\::Pro v¹echny vrcholy~$v$, do kterých vede hrana z~$u$:
\:::Je-li $D(u)+\ell(u,v) < D(v)$:
\::::$D(v) \leftarrow D(u) + \ell(u,v)$
\::::$P(v) \leftarrow u$
\::::$Z(v) \leftarrow {\bf O}$
\endalgo

\bigskip

\vbox{\raggedright
{\sem Vìta:} Pokud se alg. zastaví, pak $\forall v \; D(v)=d(v_0,v)$ a graf $C=(V_C,E_C)$,
$V_C=\{ v\in V \mid Z(v)\ne{\bf N} \}, E_C = \{ \left( v,P(v) \right) \mid v\in V_C \land P(v)\ne\? \}$,\\
je {\sit strom nejkrat¹ích cest.}
}

\endslide

\slide{Nejkrat¹í cesty: Dijkstrùv algoritmus}

$\<Dijkstra>(v_0):$

\algo
\:{\note Inicializace jako u~Prùzkumnického algoritmu}
\:Dokud existuje vrchol~$u$ takový, ¾e $Z(u)={\bf O}$:
\::Zvolíme~$u$ tak, aby $Z(u)={\bf O}$ a $D(u)$ bylo minimální.
\::{\note Prozkoumáme vrchol~$u$.}
\endalgo

\bigskip

{\sem Lemma:} Algoritmus jednou uzavøený vrchol znovu neotevøe.

{\sem Dùsledek:} Algoritmus se zastaví po nejvý¹e~$n$ prùchodech a vydá\\
vzdálenosti z~$v_0$ a strom nejkrat¹ích cest.

\endslide

\slide{Dijkstrùv algoritmus: Jádro pudla}

$\<Dijkstra>(v_0):$

\algo
\:$M\leftarrow V$ {\cmt mno¾ina nevidìných a otevøených vrcholù}
\:{\color{OliveGreen}$D(*)\leftarrow\infty$, $D(v_0)=0$} {\cmt Insert}
\:Dokud $M\ne\emptyset$:
\::{\color{OliveGreen}Zvolíme $u\in M$, jeho¾ $D(u)$ je minimální.} {\cmt DeleteMin}
\::{\color{OliveGreen}$M\leftarrow M\setminus\{u\}$}
\::Je-li $D(u)=\infty$, skonèíme.
\::Pro v¹echny vrcholy~$v$, do kterých vede hrana z~$u$:
\:::{\color{OliveGreen}$D(v) \leftarrow \min( D(v), D(u)+\ell(u,v))$ {\cmt Decrease} \\
{\note (nutné pouze pokud $v\in M$)}}
\endalgo

\bigskip

{\sem Pozorování:} Potøebujeme datovou strukturu pro uchování v¹ech $D(\cdot)$,
která bude umìt operace {\color{Blue}\<Insert>}, {\color{Blue}\<DeleteMin>} a {\color{Blue}\<Decrease>}.

\medskip

Èasová slo¾itost pak bude $\O(n\cdot T_{\hbox{\ifonts Ins}} + n\cdot T_{\hbox{\ifonts DelMin}} + m\cdot T_{\hbox{\ifonts Dec}})$.

\endslide

\end
