Bellman-Fordův algoritmus najde nejkratší cestu v orientovaném grafu s libovolným ohodnocením hran.

Na chvíli předpokládejme, že graf neobsahuje záporný cyklus. Později si ukážeme, jak rozpoznat, zda ho graf obsahuje.

Budeme postupovat podobně jako v Dijkstrově algoritmu. Pro každý vrchol $v$ si budeme udržovat hodnotu $\ARRAY{d}{v}$, která odpovídá délce nějaké cesty vedoucí z $s$ do $v$ (ne nutně té nejkratší). Cena $\ARRAY{d}{v}$ je vždy horním odhadem pro cenu nejkratší cesty do $v$. V průběhu algoritmu budeme tento odhad vylepšovat.

Na začátku u všech vrcholů kromě počátečního vrcholu $s$ nastavíme $\ARRAY{d}{v}$ na nekonečno a hodnotu $\ARRAY{d}{s}$ na nulu.

Teď si vysvětlíme, co je to update hrany. Pokud víme, že se do vrcholu $u$ umíme dostat za cenu $\ARRAY{d}{u}$ a že $uv$ je hrana, tak se umíme dostat do vrcholu $v$ za cenu $\ARRAY{d}{u} + c(uv)$ (cestu vedoucí do $u$ prodloužíme o hranu $uv$). Hrana $uv$ je korektní, pokud $\ARRAY{d}{v} \leq \ARRAY{d}{u} + c(uv)$. V opačném případě je hrana $uv$ nekorektní a můžeme zlepšit odhad $\ARRAY{d}{v}$. Kontrolu korektnosti hrany $uv$ a případnou opravu zajistí procedura update:

procedure update($u$,$v$) 
	 $\ARRAY{d}{v}:=\min\{ \, \ARRAY{d}{v},\; \ARRAY{d}{u}+c(u,v) \,\}$

Důležité vlastnosti updatování hrany jsou:

  • Nastaví správnou hodnotu $\ARRAY{d}{v}$ v případě, že $u$ je předposlední vrchol na nejkratší cestě do $v$ a hodnota $\ARRAY{d}{u}$ už je správně nastavena.
  • Nikdy nemůže zmenšit hodnotu $\ARRAY{d}{v}$ pod cenu nejkratší cesty do $v$. V tomto ohledu je použití updatování hrany bezpečné.

Nechť $s e_1 v_1 e_2 v_2\,\dots\,v_{k-1} e_{k} v_k$ je nejkratší cesta z $s$ do $v_k$. Podle první vlastnosti updatování hrany postupné zavolání procedury update na hrany $e_1$, $e_2$,…, $e_{k}$ zajistí, že $\ARRAY{d}{v}$ bude obsahovat cenu nejkratší cesty z $s$ do $v_k$. Mezi updatováním jednotlivých hran cesty jsme mohli updatovat ještě i jiné hrany grafu, ale ty výslednou hodnotu $\ARRAY{d}{v}$ neovlivní.

Na Dijkstrův algoritmus se můžeme nyní dívat jako na řadu volání procedury update ve správném pořadí. Abychom dostali správný výsledek i v případě záporných hran, musíme používat updatování hran o něco opatrněji.

V jakém pořadí updatovat jednotlivé hrany, abychom updatovali hrany na nejkratší cestě ve správném pořadí? Každá cesta má nejvýše $n-1$ hran. Stačí tedy v $(n-1)$ iteracích updatovat všechny hrany grafu. Jinými slovy posloupnost

$$\underbrace{ e_1\,e_2\,\dots\,e_m\,e_1\,e_2\,\dots\, e_m\, e_1\,\dots \kern 1cm \dots \, e_m }_{(n-1)\times}$$

má $(n-1) m$ hran a obsahuje každou posloupnost $n-1$ hran jako podposloupnost. Tím pádem updatujeme každou posloupnost $n-1$ hran ve správném pořadí. Celkem se provede $\OO(nm)$ updatů. Tomuto algoritmu se říká Bellman-Fordův algoritmus.

	 $\forall\,v\in V(G)\,:\,\ARRAY{d}{v}:= \infty$
	 $\ARRAY{d}{s}:=0$
	 for $i:=1$ to $n-1$ do
		 for all $e\in E(G)$ do
			  update($e$)

Poznámka k implementaci: v celé řadě případů obsahuje nejkratší cesta mnohem méně než $n-1$ hran. Proto můžeme skončit po méně jak $n-1$ iteracích. Z toho důvodu se vyplatí v každé iteraci zjišťovat, jestli byla některá hrana nekorektní a tedy jestli vůbec proběhl update nějaké hrany. Pokud ne, tak jsou všechny hrany grafu korektní, algoritmus by v další iteraci také neprovedl žádný update a proto můžeme skončit.

Detekce záporných cyklů

Na začátku jsme předpokládali, že graf neobsahuje záporný cyklus. Ale co když ano? Jak to poznáme? Ukázali jsme si, že když v grafu nebude záporný cyklus, tak Bellman-Fordův algoritmus najde nejkratší cestu a skončí v momentě, kdy jsou všechny hrany korektní.

Pokud graf obsahuje záporný cyklus, tak bude v grafu neustále existovat nekorektní hrana (podél cyklu můžeme odhady na cenu vylepšovat do nekonečna).

Proto stačí použít Bellman-Fordův algoritmus a po jeho skončení otestovat, jestli jsou všechny hrany grafu korektní. Pokud ano, tak algoritmus nalezl nejkratší cestu, pokud ne, tak nejkratší řešení neexistuje.

Příklad: V následujícím ohodnoceném grafu najdeme nejkratší cesty z vrcholu $A$ do všech ostatních vrcholů. Hrany máme zadané v pořadí AC, AD, BA, BE, CB, CE, DC, DE. Průběh Bellman-Fordova algoritmu je částečně zachycen tabulkou, která pro každý vrchol $v$ obsahuje hodnoty $\ARRAY{d}{v}$ na konci každé iterace.






Vrchol Iterace 0 Iterace 1 Iterace 2 Iterace 3 Iterace 4
A $0$ $0$ $0$ $0$ $0$
B $\infty$ $15$ $14$ $14$ $14$
C $\infty$ $7$ $7$ $7$ $7$
D $\infty$ $10$ $10$ $10$ $10$
E $\infty$ $10$ $6$ $5$ $5$