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
Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.
Koupit tento kurz
Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.
- Neomezený a trvalý přístup k jednotlivým lekcím.
- Kvalitní znalosti v oblasti IT.
- Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.
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.
Kredity 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íť.