Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

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

Znalosti v hodnotě stovek tisíc získáš za pár korun

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

Koupit všechny aktuálně dostupné lekce s funkcí odevzdávání úloh za pouhých 100 Kč
Aktuální stav konta 0 Kč
Koupí tohoto balíčku získáš přístup ke všem 9 článkům (9 lekcí) tohoto kurzu.

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

Co od nás v dalších lekcích dostaneš?
  • 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íť.

Článek pro vás napsal Ondřej Michálek
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