slides/dijkstra.tex

   1 \input slidemac.tex
   2
   3 \language=\czech
   4 \chyph
   5
   6 \def\note{\color{RawSienna}}
   7 \def\cmt{~~\color{Blue}}
   8
   9 \slide{Nejkrat¹í cesty: Prùzkumnický algoritmus}
  10
  11 $\<Hledej>(v_0):$
  12
  13 \algo
  14 \:$Z(*)\leftarrow{\bf N}$, $Z(v_0)={\bf O}$ {\cmt znaèky: {\sem N}evidìn, {\sem O}tevøen, {\sem U}zavøen}
  15 \:$D(*)\leftarrow\infty$, $D(v_0)=0$ {\cmt odhady vzdáleností}
  16 \:$P(*)\leftarrow ?$ {\cmt pøedchùdci, ?=nedefinováno}
  17 \:Dokud existuje vrchol~$u$ takový, ¾e $Z(u)={\bf O}$:
  18 \::{\note Prozkoumáme vrchol~$u$, èili:}
  19 \::$Z(u)\leftarrow{\bf U}$
  20 \::Pro v¹echny vrcholy~$v$, do kterých vede hrana z~$u$:
  21 \:::Je-li $D(u)+\ell(u,v) < D(v)$:
  22 \::::$D(v) \leftarrow D(u) + \ell(u,v)$
  23 \::::$P(v) \leftarrow u$
  24 \::::$Z(v) \leftarrow {\bf O}$
  25 \endalgo
  26
  27 \bigskip
  28
  29 {\sem Vìta:} Pokud se algoritmus zastaví, pak $\forall v \; D(v)=d(v_0,v)$ a graf \\
  30 $C=(V,\{ \left( v,P(v) \right) \mid v\in V \land D(v)\ne\infty \})$ je strom nejkrat¹ích cest.
  31
  32 \endslide
  33
  34 \slide{Nejkrat¹í cesty: Dijkstrùv algoritmus}
  35
  36 $\<Dijkstra>(v_0):$
  37
  38 \algo
  39 \:{\note Inicializace jako u~Prùzkumnického algoritmu}
  40 \:Dokud existuje vrchol~$u$ takový, ¾e $Z(u)={\bf O}$:
  41 \::Zvolíme~$u$ tak, aby $Z(u)={\bf O}$ a $D(u)$ bylo minimální.
  42 \::{\note Prozkoumáme vrchol~$u$.}
  43 \endalgo
  44
  45 \bigskip
  46
  47 {\sem Lemma:} Algoritmus jednou uzavøený vrchol znovu neotevøe.
  48
  49 {\sem Dùsledek:} Algoritmus se zastaví po nejvý¹e~$n$ prùchodech a vydá\\
  50 vzdálenosti z~$v_0$ a strom nejkrat¹ích cest.
  51
  52 \endslide
  53
  54 \slide{Dijkstrùv algoritmus: Jádro pudla}
  55
  56 $\<Dijkstra>(v_0):$
  57
  58 \algo
  59 \:$M\leftarrow V$ {\cmt mno¾ina nevidìných a otevøených vrcholù}
  60 \:{\color{OliveGreen}$D(*)\leftarrow\infty$, $D(v_0)=0$} {\cmt Insert}
  61 \:Dokud $M\ne\emptyset$:
  62 \::{\color{OliveGreen}Zvolíme $u\in M$, jeho¾ $D(u)$ je minimální.} {\cmt DeleteMin}
  63 \::{\color{OliveGreen}$M\leftarrow M\setminus\{u\}$}
  64 \::Je-li $D(u)=\infty$, skonèíme.
  65 \::Pro v¹echny vrcholy~$v$, do kterých vede hrana z~$u$:
  66 \:::{\color{OliveGreen}$D(v) \leftarrow \min( D(v), D(u)+\ell(u,v))$ {\cmt Decrease} \\
  67 {\note (nutné pouze pokud $v\in M$)}}
  68 \endalgo
  69
  70 \bigskip
  71
  72 {\sem Pozorování:} Potøebujeme datovou strukturu pro uchování v¹ech $D(\cdot)$,
  73 která bude umìt operace {\color{Blue}\<Insert>}, {\color{Blue}\<DeleteMin>} a {\color{Blue}\<Decrease>}.
  74
  75 \medskip
  76
  77 Èasová slo¾itost pak bude $\O(n\cdot T_{\hbox{\ifonts Ins}} + n\cdot T_{\hbox{\ifonts DelMin}} + m\cdot T_{\hbox{\ifonts Dec}})$.
  78
  79 \endslide
  80
  81 \end