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