Motivace: Silniční síť si můžeme znázornit grafem. Křižovatky odpovídají vrcholům grafu a silnice mezi nimi hranám. Každý úsek silnice odpovídající hraně má svojí délku. Ta odpovídá ohodnocení hrany. Můžeme se ptát jaká je nejkratší cesta z Prahy do Ostravy? Kolik je to kilometrů a kudy vede? Maximální povolená rychlost na každém úseku silnice nám říká, jak rychle po ní můžeme jet. Z rychlosti a délky silnice se dá dopočítat, za jak dlouhou úsek silnice projedeme. Proto se můžeme ptát i na nejrychlejší cestu z Prahy do Ostravy. Nejrychlejší cesta nemusí být zrovna nejkratší.

Problém hledaní nejkratší cesty v grafu a jemu podobné problémy se vyskytují téměř všude: při hledání autobusového nebo vlakového spojení v online jízdních řádech, při hledání optimální cesty v navigacích do aut, při plánování pohybu robotů a nebo při routování paketů v internetu.

Definice: Co to je vzdálenost? Vzdálenost je matematicky popsána pojmem metrika.
Nechť M je neprázdná množina. Metrika je zobrazení $\rho : M\times M \to \RR_+$, které pro libovolné $x,y\in M$ splňuje axiomy:

  1. (totožnost): $\rho(x,y)=0$ právě tehdy když $x=y$
  2. (symetrie): $\rho(x,y)=\rho(y,x)$
  3. (trojúhelníková nerovnost): $\rho(x,z) \leq \rho(x,y)+\rho(y,z)$.

Z prvního a třetího axiomu vyplývá nezápornost metriky $\rho(x,y)\geq 0$. Číslu $\rho(x,y)$ říkáme vzdálenost bodů $x$ a $y$. Nechť $p_1=(x_1, y_1)$ a $p_2=(x_2, y_2)$ jsou dva body v rovině.


Mezi nejpoužívanější metriky v rovině patří:

  • eukleidovská metrika — vzdálenost $p_1$ a $p_2$ je délka úsečky $p_1 p_2$, neboli vzdálenost vzdušnou čarou.
  • maximová metrika — vzdálenost $p_1$ a $p_2$ je maximum z $|x_1-x_2|$ a $|y_1-y_2|$.
  • manhattanská metrika — po Manhattanu v New Yorku se chodí v síti pravoúhlých ulic, které jsou rovnoběžné s osami souřadného systému. Vzdálenost $p_1$ a $p_2$ je $|x_1-x_2|+|y_1-y_2|$.

My si v této kapitole vystačíme se vzdáleností v grafech, tj. s grafovou metrikou. Nechť $G$ je graf s ohodnocením hran $c: E(G)\to\RR$. Číslo $c(e)$ se nazývá cena hrany $e$, ale v kontextu hledání nejkratší cesty mu budeme říkat délka hrany $e$. Délka cesty $x=v_0 e_1 v_1 e_2 \dots v_{k-1} e_{k}
v_{k}=y$ se počítá jako $\sum_{i=1}^{k} c(e_i)$. Vzdálenost dvou vrcholů $x$ a $y$ v grafové metrice je délka nejkratší cesty mezi $x$ a $y$.

Úkol (Shortest path): Dostaneme graf $G$ s ohodnocením hran $c: E\to\RR$, počáteční vrchol $s$ a cílový vrchol $t$. Chceme nalézt nejkratší cestu z $s$ do $t$.

Všechna prakticky používaná řešení místo výše uvedeného problému řeší problém obecnější. Místo jedné cesty z $s$ do $t$ hledáme nejkratší cestu z $s$ do všech ostatních vrcholů.

Úkol (Single source shortest path): Dostaneme graf $G$ s ohodnocením hran $c: E\to\RR$, počáteční vrchol $s$. Chceme nalézt nejkratší cestu z $s$ do všech ostatních vrcholů $v\in V(G)$.

Předchozí úkol můžeme ještě více zobecnit.

Úkol (All pairs shortest path): Dostaneme graf $G$ s ohodnocením hran $c: E\to\RR$ a chceme nalézt nejkratší cestu mezi každou dvojicí vrcholů.

Nejkratší cesta splňuje princip optimality. Ten říká, že každá podcesta nejkratší cesty je také nejkratší cestou mezi svými koncovými vrcholy. Přesněji řečeno, je-li $xPy$ nejkratší cesta z $x$ do $y$ a $u$,$v$ jsou dva vrcholy na $P$, tak je i úsek $uPv$ nejkratší cestou mezi $u$ a $v$. Pokud mezi $u$ a $v$ existuje kratší cesta $uQv$, tak v původní cestě $xPy$ nahradíme úsek $uPv$ cestou $uQv$ a dostaneme kratší cestu. To je spor.

Podívejme se na to, jak by měl vypadat výstup řešení druhého úkolu. V každém vrcholu $v$ si budeme pamatovat předchůdce $\pi(v)$ na nejkratší cestě do $s$. Jednoduše řečeno, $\pi(v)$ je směrovka říkající kudy máme vrchol $v$ opustit, abychom se dostali zpět do vrcholu $s$ po nejkratší cestě. Je-li je graf $G$ souvislý, tak z každého vrcholu $v$ existuje cesta do $s$ a každý vrchol kromě $s$ má právě jednoho předchůdce $\pi(v)$ na nejkratší cestě.1 Hrany $\{v,\pi(v)\}$ tvoří strom orientovaný do kořene $s$, který nazveme strom nejkratší cesty. Cílem hledání nejkratší cesty v grafu je najít strom nejkratší cesty.2

Protože ve městech kromě běžných silnic existují i jednosměrky, tak je zcela přirozené hledat nejkratší cestu i v orientovaných grafech. Vzdálenost dvou vrcholů $s$ a $t$ v orientovaném grafu je opět délka nejkratší orientované cesty z $s$ do $t$.3 Všechny algoritmy, které si v této kapitole uvedeme, fungují i pro orientované grafy. Není to nic překvapivého, vždyť i neorientovaný graf, ve kterém hledáme cestu, máme reprezentovaný jako orientovaný graf. Každou hranu si pamatujeme jako dvě orientované hrany/šipky vedoucí proti sobě.