Bellman-Fordův algoritmus slouží k nalezení nejkratších cest ze zadaného uzlu do všech ostatních uzlů grafu, který neobsahuje cyklus záporné délky. V případě, že jej graf obsahuje, je algorimus schopen jeho detekce.
Algoritmus byl vymyšlen americkými matematiky Richardem Bellmanem a Lesterem Fordem.
Princip
Základem Bellman-Fordova algoritmu je operace relaxace. Do této operace vstupují dva uzly a hrana, která mezi nimi vede. Pokud je vzdálenost zdrojového uzlu sečtená s délkou hrany menší než aktuální vzdálenost cílového uzlu, tak se za předchůdce cílového uzlu na nejkratší cestě označí zdrojový uzel (a vzdálenost cílového uzlu se přepočítá). V případě nesplnění nerovnosti tato hrana cestu nezkracuje a neprovádí se proto žádné změny.
Délka cesty ze zdrojového do každého z cílových uzlů může být dlouhá maximálně hran (protože by jinak musela obsahovat cyklus). Proto pokud pustíme operaci relaxace na všechny hrany grafu
krát, tak již musí být nalezeny všechny nejkratší cesty. Toto ověříme ještě jedním spuštěním relaxací všech hran. Pokud dojde k nějaké relaxaci, tak graf obsahuje cyklus záporné délky, pokud k relaxaci nedojde, algoritmus může vrátit výsledek.
Kód
function <predecessors> Bellman-Ford(G, source)
for i in 1 to |U| do
distance[i] = +inf
predecessors[i] = null
distance[source] = 0
for i in 1 to (|U| - 1) do
for each Edge e in Edges(G) do
if distance[e.from] + length(e) < distance[e.to] do
distance[e.to] = distance[e.from] + length(e)
predecessors[e.to] = e.from
for each Edge e in Edges(G) do
if distance[e.from] + length(e) < distance[e.to] do
error("Graf obsahuje cyklus zaporne delky")
return predecessors
Složitost
Asymptotická složitost algoritmu je , protože vnější smyčka proběhne právě
krát a vnitřní smyčka probíhá přes všechny hrany grafu.
Příklad
Literatura
- KOLÁŘ, Josef. Teoretická informatika. 2. vyd. Praha : Česká informatická společnost, 2004. 205 s. ISBN 80-900853-8-5.