Lekce 5 - Implementace Dijkstrova algoritmu - 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.
Dijkstrův algoritmus je nejpopulárnější a nejpoužívanější algoritmus na hledání nejkratší cesty v grafu. Myšlenka je jednoduchá. Chceme znát nejkratší cestu z jednoho uzlu do všech ostatních. K odstartování potřebujeme kromě grafu znát počáteční uzel.
Tento článek je velmi technický a věnuje se konkrétní implementaci algoritmu v jazyce Java. Jelikož používá jen základní syntaxi, tak při drobné změně struktur se dá algoritmus lehce převést do libovolného programovacího jazyka. Jelikož je algoritmus složitější, zejména díky dalším strukturám, které si musíme definovat, je jeho implementace a teorie takto rozdělena.
Algoritmus
Na úvod si alespoň stručně zopakujme jak algoritmus funguje.
Vstup
Na stupu máme ohodnocený graf G a počáteční vrchol
s.
Výstup
Jako výstup požadujeme:
- pole vzdáleností, udávající nejkratší vzdálenosti
mezi uzlem
ua všemi ostatními - pole předchůdců
Popis algoritmu
Pro každý vrchol v máme 3 možné stavy:
...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 rozebereme implementaci Dijkstrova algoritmu, koukneme se na úskalí a ukážeme si, jak rozložit původní algoritmus na jednoduché objekty.
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íť.
