Dijkstrův algoritmus1 najde nejkratší cestu v orientovaném grafu s nezáporným ohodnocením hran. Už jsme si ho jednou odvodili pomocí adaptace průchodu do šířky (viz předchozí podsekce). Nyní si ho ukážeme znova a nezávisle. Zdůrazněme raději ještě jednou, že ohodnocení hran grafu musí být nezáporné, jinak nebudeme moci zaručit správnost algoritmu.

Nejprve si vysvětlíme význam proměnných, které budeme používat. Množina $T \subseteq V$ je množina trvalých vrcholů, to je těch, do kterých známe nejkratší cestu (a do kterých už došli Číňané). Hodnota $\ARRAY{d}{v}$ délka nejkratší cesty z $s$ do $v$ vedoucí jen přes trvalé vrcholy a proto je horním odhadem na vzdálenost z $s$ do $v$ (víceméně odpovídá času, na který je nastaven budík). Do pole $\ARRAY{odkud}{v}$ si ukládáme předchůdce na nejkratší cestě z $s$ do $v$ (odkud jsme do $v$ přišli po nejkratší cestě).

Začneme s prázdnou množinou $T$, vzdálenost do startu $\ARRAY{d}{s}$ nastavíme na $0$ a odhady vzdáleností do ostatních vrcholů na nekonečno. Postupně budeme odebírat netrvalé vrcholy s minimálním $\ARRAY{d}{v}$ a prohlašovat je za trvalé. Během prohlašování musíme aktualizovat odhady $\ARRAY{d}{w}$ u ostatních vrcholů $w$, protože jsme se do nich mohli dostat zkratkou z nově prohlášeného trvalého vrcholu $v$.

$T:=\emptyset$
$\ARRAY{d}{s}:=0$ a $\forall\,v\in V\setminus\{s\}\,:\,\ARRAY{d}{v}:=\infty$
$\forall\,v\in V\,:\,\ARRAY{odkud}{v}:=nil$

vytvoř prioritní frontu $H$ z vrcholů $V$ s prioritami $\ARRAY{d}{v}$
while fronta $H$ neprázdná do
	 $v := DELMIN(H)$ 		 {vyber netrvalý vrchol s nejmenším $\ARRAY{d}{v}$}
	 $T:=T\cup \{v\}$
	 for each $vw\in E$ do
		 if $\ARRAY{d}{w}> \ARRAY{d}{v}+c(vw)$ then
			 $\ARRAY{d}{w}:=\ARRAY{d}{v}+c(vw)$
			 $\ARRAY{odkud}{w}:=v$
			 $DECREASEKEY(H,w)$ 	 {aktualizuj haldu}

O realizaci operací $\DELMIN$ a $\DECREASEKEY$ se dočtete v kapitole o haldě.2 Algoritmus je konečný, protože v každé iteraci prohlásí jeden vrchol za trvalý. Vrcholů je jen $n$ a z každého vede nejvýše $n$ hran.

Pro každý vrchol $x$, do kterého neexistuje cesta ze startu $s$, zůstane po skončení algoritmu $\ARRAY{d}{x}=\infty$. Proto můžeme už v průběhu algoritmu testovat, jestli je $\ARRAY{d}{v}$ vybraného vrcholu $v$ rovno nekonečnu a případně skončit (k žádným změnám už by stejně nedošlo). Podobně pokud hledáme pouze nejkratší cestu do vrcholu $t$ a ne do všech vrcholů, tak můžeme skončit v momentě, kdy bude $t$ prohlášen za trvalý.

Časová složitost Dijkstrova algoritmu odpovídá času potřebnému na provedení $n\times \DELMIN$ a $m\times \DECREASEKEY$. Stačí tedy dosadit časové složitosti těchto haldových operací. Prioritní frontu můžeme implementovat v poli — pak dostaneme celkový čas $\OO(n^2+m)$, a nebo pomocí binární haldy — dostaneme celkový čas $\OO((m+n)\log n)$. Kterou implementaci si máme vybrat? To záleží, jestli je graf hustý (má hodně hran) a nebo řídký (má málo hran). V každém grafu $G$ je $m < n^2$. Pokud je počet hran $m = \Omega(n^2)$, tak je implementace v poli rychlejší. Když počet hran klesne pod $n^2/\log n$, tak už se vyplatí binární halda.

Můžete se ptát, jak to dopadne, pokud použijeme $d$-regulární haldu, která pro vhodná $d$ zobecňuje obě předchozí řešení. Ale jak zvolit parametr $d$? Časová složitost Dijkstrova algoritmu s $d$-regulární haldou je $\OO( (nd + m){\log n \over \log d} )$. Po chvilce počítání3 se ukáže, že nejvýhodnější volba je $d \approx m/n$ (průměrný stupeň grafu). Pro velmi řídké grafy s $m=\OO(n)$ dostaneme časovou složitost $\OO(n\log n)$, stejně jako u řešení s binární haldou. Pro husté grafy s $m=\Omega(n^2)$ dostaneme lineární4 časovou složitost $\OO(n^2)$, stejně jako u řešení s polem. Pro grafy se střední hustotou $m= n^{1+\delta}$ dostaneme také lineární časovou složitost $\OO(m/\delta)=\OO(m)$.

Zbývá dokázat správnost Dijkstrova algoritmu.

Invariant: Pro každý trvalý vrchol $v$ je $\ARRAY{d}{v}$ délka nejkratší cesty z $s$ do $v$.

Invariant dokážeme indukcí podle prohlašování vrcholů za trvalé. Pro počáteční vrchol $s$ to platí. Předpokládejme, že v momentě před prohlášením $v$ za trvalý vrchol, invariant platí pro všechny vrcholy z množiny $T$. Ukažme indukční krok tj., že v ten moment je $\ARRAY{d}{v}$ délka nejkratší cesty z $s$ do $v$.

Předpokládejme pro spor, že existuje kratší cesta $sPv$. Nechť $uw_1$ je první hrana na cestě $P$ vedoucí z trvalého do netrvalého vrcholu. Taková hrana určitě existuje, protože $s$ je trvalý vrchol, ale $v$ už trvalý není. Z volby vrcholu $v$ jako netrvalého vrcholu s minimálním $\ARRAY{d}{v}$ vyplývá $\ARRAY{d}{w_1} \geq \ARRAY{d}{v}$.

Z indukčního předpokladu je $\ARRAY{d}{u}$ délka nejkratší cesty z $s$ do $u$. Při prohlašování vrcholu $u$ za trvalý jsme zkoušeli snížit hodnotu $\ARRAY{d}{w_1}$ na $\ARRAY{d}{u}+c(u w_1)$. To se buď povedlo a nebo už byla hodnota $\ARRAY{d}{w_1}$ nižší. Proto je $\ARRAY{d}{w_1}\leq\ARRAY{d}{u}+c(u w_1)$.

Označme další vrcholy na cestě $w_1Pv$ jako $w_2$, $w_3$,…, $w_k$. Protože všechny hrany mají nezáporné ohodnocení, tak $c(sPv) = \ARRAY{d}{u}+c(u w_1) +c(w_1w_2)+\dots+c(w_k v)
\geq \ARRAY{d}{w_1}\geq \ARRAY{d}{v}$. A to je spor s tím, že $sPv$ je kratší cesta do $v$.

Příklad: V následujícím grafu pomocí Dijkstrova algoritmu najdeme nejkratší cestu z vrcholu A do všech ostatních vrcholů. Průběh Dijkstrova algoritmu je zachycen na obrázcích vpravo po řádcích. Množina trvalých vrcholů je zakroužkována. Šipky znázorňují strom nejkratší cesty na trvalých vrcholech.