Lekce 6 - Implementace algoritmu Bellman-Ford - Nejkratší cesta grafu

V minulé lekci, Implementace Dijkstrova algoritmu - Nejkratší cesta grafu, jsme si ukázali implementaci Dijkstrova algoritmu.

S teorií okolo hledání nejkratší cesty v grafu jsme se již setkali v lekci Hledání nejkratší cesty v grafu, kde také naleznete další teorii k problematice hledání nejkratší cesty v grafu.

V tomto článku se budeme věnovat samotné implementaci algoritmu Bellman-Ford. Ten je podobný Dijkstrovi, běží však i na grafu se zápornými hranami. Dokonce odhalí i záporný cyklus.

Popis algoritmu

Pro ilustraci si na úvod zopakujme, jak algoritmus funguje, než se pustíme do jeho implementace.

Vstup

Vstupem je ohodnocený graf G a počáteční uzel s (start).

Výstup

Výstupy je pole vzdáleností, udávající nejkratší vzdálenosti mezi uzlem s a všemi ostatními a pole předchůdců. Dalším výstupem je detekce záporného cyklu.

Průběh

Pro každý vrchol v :
        ohodnocení(v) = nekonečno
    předchůdci_vrcholu[v] = null // chceme si pamatovat cestu, kudy jdeme, zde je prázdná
ohodnoceni(s) = 0

pro každý další vrchol u
    pro každý vrchol v
        pokud ohodnocení (u) + vzdálenost(u,v) < ohodnocení(v)
            ohodnoceni(v) = ohodnocení (u) + vzdálenost(u,v)
            předchůdce_vrcholu(v).add(u)

Pro každý vrchol u
    pro každý vrchol v
        pokud ohodnocení (u) + vzdálenost(u,v) < ohodnocení(v)
                      vypis "ERROR, zaporny cyklus"

Algoritmus se skládá víceméně ze 3 částí:

...konec náhledu článku...
Pokračuj dál