\input ../lecnotes.tex

\prednaska{5}{Nejkrat¹í cesty}{}

Na~této pøedná¹ce budeme studovat problém hledání nejkrat¹ích cest
v~orientovaných grafech ohodnocených reálnými èísly.

\s{Situace:} Máme orientovaný graf~$G$ a funkci $l : E(G) \rightarrow {\bb R}$
pøiøazující hranám jejich ohodnocení (délky). Pro vrcholy $u,v\in V(G)$ budeme
chtít spoèítat jejich vzdálenost $d(u,v)$, co¾ bude délka nejkrat¹í cesty z~$u$
do~$v$ nebo $\infty$, pokud ¾ádná cesta neexistuje.

Aby se vzdálenosti chovaly \uv{rozumnì} tedy co nejvíce jako metrika. Orientovanost
grafù nám kazí symetriènost -- nemusí nutnì platit $d(x, y)=d(y, x)$. Budeme aspoò chtít,
aby platily následující vlastnosti:

\itemize\ibull
\:$d(u, u) = 0$,
\:$d(u, v) \leq d(u, w) + d(w, v)$ (trojúhelníková nerovnost).
\endlist

To nemusí obecnì platit (kazí nám to záporné cykly), proto budeme studovat
pouze grafy, v~nich¾ záporné cykly neexistují. Pak u¾ budou obì vlastnosti
splnìny, jak plyne napøíklad z~následujícího lemmatu:

\s{Lemma:}
V~grafu bez záporných cyklù existuje ke~ka¾dému nejkrat¹ímu sledu z~$u$ do~$v$ stejnì dlouhá $uv$-cesta.

\proof Máme-li nejkrat¹í $uv$-sled, který není cestou, opakuje se v~nìm nìjaký vrchol
$w \in V(G)$. 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. \qed

\s{Jednoduché pøípady}


\itemize\ibull
\:Pokud $l$ je konstantní funkce, pou¾ijeme BFS. Èasová slo¾itost bude $\Theta(m+n)$.
\:Délky hran jsou malá pøirozená èísla $l(x, y) \in\{1, \dots, L\}$ podrozdìlíme hrany
a pou¾ijeme BFS. Èasová slo¾itost $\Theta(Lm+n)$.
\:DAG (orientovaný acyklický graf) indukcí pøes topologické uspoøádání v èase
$\Theta(m+n)$.
\endlist

\s{Definice:} $D_k(v):=$ minimální délka ze sledù z $v_0$ do $v$ o právì k hranách.
$D_0(v)=0$ pokud $v=v_0$, jinak $D_0(v)=\infty$.
$d(v_0, v)=\min D_k(v)$

Kdy¾ známe $D_0 \dots D_{k-1}$ spoèteme $D_k=\min D_{k-1}(u)+l(u, v)$.

Naivní implementace pobì¾í $n(\sum_v deg^+(v))+n$ (musíme pøièíst na
konec $n$ za izolované vrcholy), úpravíme $\sum_v deg^+(v)=m$. Bohu¾el
spotøebujeme $\Theta(n^2)$ pamìti.

Nevýhodou této implementace je pøistupování k hranám pozpátku.

\s{Bellman-Fordùv algoritmus}
\algo
\:$D(*) \leftarrow \infty, D(s) \leftarrow 0$
\:Pro $k=1, \dots, n-1$:
\::$D_k(*) \leftarrow \infty$
\::Pro $\forall v\in V(G)$:
\:::Pro $\forall w (v, w)\in E(G)$:
\::::$D(w)\leftarrow \min(D(w), D_{k-1}(v)+l(v, w))$
\endalgo

Pokud by i v $n$-tém kroku nìco vykonal, graf obsahuje záporný cyklus.

\s{Vìta:} Bellman--Fordùv algoritmus najde v èase $\Theta(nm)$ vzdálenosti $d(v_0, v)$
pro $\forall v\in V(G)$.

\proof
Invarianty:
\itemize\ibull
\:Koneèné $D(v)$ v¾dy odpovídá délce nìjakého sledu z $v_0 \rightarrow w$
\:Na konci k-tého prùchodu vnìj¹m cyklem platí $D(w)\leq \min$ délka sledu z $v_0
\rightarrow v$ o ménì ne¾ $k$ hranách z toho plyne ¾e na konci $D(w)\leq d(v_0, v)$

Nech» nejkrat¹í sled $v_0\rightarrow w$ o ménì ne¾ $k$ hranách konèí hranou $(v, w)$,
zastavme algoritmus v okam¾iku kdy v $k$-tém prùchodu zpravovává hranu $(v, w)$ tehdy
$D(w)\leq D(v)+l(v, w)$ a $D(v)$ je dle indukèního pøedpokladu men¹í nebo rovný
minimální délce sledu $v_0\rightarrow v$ o $\leq k$ hránách.
\endlist
\qed

\s{"Prùzkumnický algoritmus"}
Stav: $D(v)$ je ohodnoceníí, $S(v)$ stav (vidìn, otevøen -- od posledního prozkoumání
se $D(v)$ zmìnilo, zavøen není potøeba zkoumat znovu, nic by se nezmìnilo).

\algo
\:$D(*)\leftarrow \infty, D(v_0)=0, S(*)\leftarrow N, S(v_0)\leftarrow O,
P(*)\leftarrow ?$
\:Dokud $\exists u$: $S(u)=O$ opakuj:
\::$S(u)\leftarrow Z$
\::Pro $\forall v: (u, v)\in E(G)$:
\:::Je-li $D(u)+l(u, v)<D(v)$
\::::$D(v)\leftarrow D(u)+l(u, v)$
\::::$S(v)\leftarrow O$
\endalgo

\s{Invariant} $D(v)$ neroste a odpovídá délce nìjakého sledu z $v_0$ do $v$.

\s{Lemma} algoritmus se v¾dy zastaví, èas pøi nevhodném zavírání mù¾e být a¾
exponenciální. Toto lemma bude bez zanecháno bez dùkazu.

Pokud se zastaví, pak dosa¾itelné vrcholy jsou zavøené a $S(v)=Z$ pak platí
$D(v)=d(v_0, v)$.

\proof
Nech» cesta z $v_0$ do $v$ je nejmen¹í protipøíklad, pak musí existovat vrchol $u$,
pro který neplatí $S(u)=Z$. Co¾ je spor, proto¾e takový vrchol musel ná¹ algoritmus
projít.

Vezmìme minimání protipøíklad co do poètu hran. Nech» $v$ je nejbli¾¹í vrchol takový
¾e $D(v)\neq d(v_0, v)$, tudí¾ musí být vìt¹í (odpovídá délce nìjakého sledu). $u:=$
pøedchùdce $v$ na nejkrat¹í cestì tedy $D(u)$ je správnì. Algoritmus zkoumal u na
nastavil finální $D(u)$, tedy zpracoval hranu $(u, v)$ a $D(v)\leq D(u)+l(u, v)$, co¾
je opravdová vzdálenost. Dostali jsme spor s tím, ¾e $D(x)$ neroste.
\qed

\bye
