Aktuálně: Postihly zákazy tvou profesi? Poptávka po ajťácích prudce roste, využij podzimní akce 30% výuky zdarma!
Pouze tento týden sleva až 80 % na e-learning týkající se JavaScript

Implementace algoritmu Bellman-Ford - Nejkratší cesta grafu

V minulé lekci, Tok v síti a Dinicův algoritmus na hledání maximálního toku, jsme si ukázali definice toku v síti, souvisejících pojmů a implementace jednoho z algoritmů na hledání maximálního toku zvaného Dinicův algoritmus.

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...

Prémiový článek

Prémiový článek

Na itnetwork.cz se nachází největší a nejucelenější česká databáze s výukovými články, jejímž cílem je umožnit kvalitní vzdělání v oblasti IT úplně každému. Měsíčně zobrazíme k milionu článků a sklidíme desítky děkovných emailů, kde nám sdělujete, že jsme vám pomohli k lepšímu zaměstnání nebo vzdělání.

Ačkoli se snažíme držet většinu obsahu úplně zadarmo, udržovat síť v provozu a aktuální stojí obrovské úsilí. Proto je nějaký obsah, jako cvičení nebo odbornější články, přístupný pouze za body. Nebojte, nestojí to skoro nic :)

Popis článku

Požadovaný článek má následující obsah:

V tomto článku se podíváme na detailní popis a implementaci algoritmu Bellman-Ford pro hledání nejkratší cesty v grafu se zápornými hranami.

Omezená nabídka: Nauč se vše a ušetři

Koupit články a funkce postupně a po jednom 40 bodů
Koupit všechny aktuálně dostupné články v sekci se všemi funkcemi za exkluzivní cenu 34 bodů
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 8 článkům s kontrolou a certifikací a ještě navíc ušetříš 15 Kč. Nabídka je omezená pouze pro první články z kurzu a obsahuje exkluzivní slevu 15%.
34 bodů získáš za přidání svého článku na síť nebo odpovídá 100 Kč 85 Kč

Pozor, pokud si koupíš pouze tento článek, ztratíš nárok na speciální slevu 15% na balíček všech článků.

Pro přístup k článku potřebuješ 10 bodů
Na svém účtu máš aktuálně 0 bodů
10 bodů získáš za přidání svého článku na síť nebo odpovídá 25 Kč

Koupí článku k němu získáš neomezený přístup a to napořád. Posuneš své znalosti zas kousek dopředu a zároveň nám pomůžeš udržovat celý projekt při životě a pomáhat vám tak k lepší budoucnosti.

Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.

Body získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.

Dobít body můžeš okamžitě např.:

Kartou SMS Převodem
Kartou SMS Převodem
Článek pro vás napsal Tricerator
Avatar
Autor se věnuje teoretické informatice. Ve svých volných chvílích nepohrdne šálkem dobrého čaje, kaligrafickým brkem a foukací harmonice.
Aktivity (2)