2007/11-dijkstra/11-dijkstra.tex

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