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ě |U|-1 hran (protože by jinak musela obsahovat cyklus). Proto pokud pustíme operaci relaxace na všechny hrany grafu |U|-1 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 O(|U| \\cdot |H|), protože vnější smyčka proběhne právě |U|-1 krát a vnitřní smyčka probíhá přes všechny hrany grafu.


Příklad

Bellman-Fordův algoritmus
Bellman-Fordův algoritmus

Literatura

  • KOLÁŘ, Josef. Teoretická informatika. 2. vyd. Praha : Česká informatická společnost, 2004. 205 s. ISBN 80-900853-8-5.







Místo pro váš banner

Zde je vyhrazené místo pro bannery našich partnerů a zákazníků.