6-dijkstra/6-dijkstra.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{6}{Dijkstrùv algoritmus a haldy}{}
   4
   5 {\bf FIXME: Nerevidováno!}
   6
   7 Na~této pøedná¹ce budeme pokraèovat v~problému hledání nejkrat¹ích cest
   8 v~grafech ohodnocených reálnými èísly. Ji¾ jsme potkali Bellmanùv-Fordùv
   9 algoritmus a jeho zobecnìní v~podobì prùzkumnického algoritmu.
  10
  11 \s{Situace:} Máme orientovany graf~$G$ a funkce $l : E(G) \rightarrow {\bb R}$
  12 pøiøazující hranám jejich ohodnocení (délky). Pro vrcholy $u,v\in V(G)$ budeme
  13 chtít spoèítat jejich vzdálenost $d(u,v)$, co¾ bude délka nejkrat¹í cesty z~$u$
  14 do~$v$ nebo $\infty$, pokud ¾ádná cesta neexistuje.
  15
  16 Aby se vzdálenosti chovaly \uv{rozumnì} (tj. jako metrika), budeme chtít, aby platily
  17 následující vlastnosti:
  18
  19 \itemize\ibull
  20 \:$d(u, u) = 0$,
  21 \:$d(u, v) \leq d(u, w) + d(w, v)$ (trojúhelníková nerovnost).
  22 \endlist
  23
  24 To nemusí obecnì platit (kazí nám to záporné cykly), proto budeme studovat
  25 pouze grafy, v~nich¾ záporné cykly neexistují. Pak u¾ budou obì vlastnosti
  26 splnìny, jak plyne napøíklad z~následujícího lemmatu:
  27
  28 \s{Lemma:}
  29 V~grafu bez záporných cyklù existuje ke~ka¾dému nejkrat¹ímu sledu z~$u$ do~$v$ stejnì dlouhá $uv$-cesta.
  30
  31 \proof
  32 Máme-li nejkrat¹í $uv$-sled, který není cestou, opakuje se v~nìm nìjaký vrchol $w \in V(G)$.
  33 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.
  34 \qed
  35
  36 Opakování: Dijkstrùv algoritmus
  37 \itemize\ibull
  38 \:$D(v)$ \dots doèasná vzdálenost z $s$ do $v$
  39 \:Znaèky $Z(v)$ \itemize\ibull
  40 \::Nevidìn
  41 \::Vidìn
  42 \::Hotov
  43 \endlist
  44 \endlist
  45
  46 %druha strana zapisku
  47 \algo
  48 \:$D(*) \leftarrow +\infty , D(s) \leftarrow 0$
  49 \:$Z(*) \leftarrow Neviden, Z(s) \leftarrow V$
  50 \:while $\exists v : Z(v) = V$
  51 \::vybereme $v : Z(v) = V, D(v) = min$
  52 \::$Z(v) = H$
  53 \::for $\forall w : (v, w) \in E(G)$
  54 \:::$D(w) \leftarrow min( D(w), D(w) + l(v, w))$
  55 \::if $Z(w) = N \Rightarrow Z(w) \leftarrow V$
  56 \endalgo
  57
  58 \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).
  59
  60 \proof Následující posloupností lemmat.\qed
  61
  62 \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.
  63
  64 \proof
  65 Pokud by tomu tak nebylo, mù¾eme $v_0,\dots,v_{k-1}$ vymìnit za~krat¹í cestu, a~tím
  66 získat krat¹í $v_0v_k$-cestu.
  67 \qed
  68
  69 \s{Lemma 2:} Algoritmus se zastaví po $\leq n$ prùchodech cyklem.
  70
  71 \proof
  72 Zøejmé z~toho, ¾e ka¾dý vrchol uzavøeme nejvý¹e jednou.
  73 \qed
  74
  75 \s{Lemma 3:} Po zastavení jsou hotovy právì vrcholy dosa¾itelné z $s$.
  76
  77 \proof
  78 Viz minulá pøedná¹ka.
  79 \qed
  80
  81 \s{Lemma 4:} $D(v)$ uzavíraných vrcholù tvoøí neklesající posloupnost.
  82
  83 \proof
  84 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)$.
  85 \qed
  86
  87 \s{Lemma 5:} Pokud $v \in H$, pak $D(v)$ se u¾ nezmìní.
  88
  89 \proof
  90 Indukcí podle bìhu algoritmu.
  91 \qed
  92
  93 \s{Lemma 6:} Pro $\forall v D(v)$ je délka nejkrat¹í $sv$-cesty, její¾ vnitøní vrcholy le¾í v¹echny v $H$.
  94
  95 \proof
  96 \itemize\ibull
  97 \:po 1. prùchodu OK
  98 \:uzavíráme-li dal¹í vrchol $v$:
  99 \itemize\relax
 100 \:a) $D(w)$ pro $w \in H$
 101 Podle Lemma 5 se $D(w)$ nemìní. Musíme nahlédnout, ¾e se opravdu zmìnit nemá.
 102 \:b) $D(w)$ pro $w \notin H$
 103 $D(w) = min{D(v) + l(v, w)}$
 104 \endlist
 105 \endlist
 106 \qed
 107
 108 Existuje pomalej¹í algoritmus pro grafy se zápornými hranami bez záporných cyklù.
 109 \s{Bellman-Fordùv algoritmus}
 110 \algo
 111 \:$D(*) \leftarrow \infty, D(s) \leftarrow 0$
 112 \:Opakuji
 113 \::Pro $\forall v \in V$
 114 \:::$prozkoumej(v)$
 115 \:::(koukne se, jestli nejde vylep¹it cestu¨
 116 \:::do sousedù $v$)
 117 \:dokud se nìjaké $D(\dots)$ mìní
 118 \endalgo
 119
 120 \s{Lemma 1:} Pokud $D(v) < \infty$, pak existuje sled z $s$ do $v$ délky $D(v)$.
 121 (speciálnì z toho plyne $\forall v D(v) \geq d(s,v)$)
 122
 123 \s{Lemma 2:} $\forall v D(v)$ nikdy neroste.
 124 \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.
 125 %ctvrta stranka
 126 \proof
 127 Indukcí\dots pro $k \geq 0$ OK
 128 Indukèní krok: Dobìhla $k-1$ fáze, pou¹tíme $k$-tou
 129
 130 \qed
 131 \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)
 132
 133 \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.)
 134
 135 Èasová slo¾itost Bellman-Fordova algoritmu : $O(n*m)$
 136
 137 \s{Floyd-Warshallùv algoritmus}
 138 $G$ je graf se záporným ohodnocením hran, bez záporných cyklù
 139 $D_{i,j}^k$ = délka nejkrat¹í cesty z $v_i$ do $v_j$ pøes $v_1 \dots v_k$
 140 %pozorovani
 141 $D_{ij}^0 = l(v_i, v_j)$, $D_{ii}^0 = 0$
 142 $D_{ij}^n = d(v_i, v_j)$ - skuteèná vzdálenost v grafu
 143 \algo
 144 \:$D_{i,j} \rightarrow l(v_i, v_j), D_{i,i} \rightarrow 0 \forall i, j$
 145 \:for $k = 1$ to n
 146 \::for $i = 1$ to n
 147 \:::for $j = 1$ to n
 148 \::::$D_{i,j} = min(D_{i,j}, D_{i,k} + D_{k,j})$
 149 \endalgo
 150
 151 \s{Vìta:} Floyd-Warshallùv algoritmus spoèítá $D_{i,j} = d(v_i, v_j)$ v èase $O(n^3)$.
 152
 153 \>Shrnutí:
 154
 155 \s{$s \rightarrow *$}
 156 Dijkstrùv algoritmus $O(n^2)$
 157 \dots s haldou $O((n+m)\log m)$
 158 \dots s regulární haldou $O(n + m*log n)$
 159 \dots s Fibbonaciho haldou $O(n*log n + m)$
 160 Bellman-Ford $O(n*m)$
 161
 162 \s{$* \rightarrow *$}
 163 Floyd-Warshall $O(n^3)$
 164
 165 \bye