Office week BF - Easter
Tento týden až 80% sleva na e-learning MS Office!
80 % bodů zdarma díky naší Velikonoční akci!

Implementace Dijkstrova algoritmu - Nejkratší cesta grafu

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

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 rozebereme implementaci Dijkstrova algoritmu, koukneme se na úskalí a ukážeme si, jak rozložit původní algoritmus na jednoduché objekty.

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

Koupit články a funkce postupně a po jednom 30 bodů
Koupit všechny aktuálně dostupné články v sekci se všemi funkcemi za exkluzivní cenu 26 bodů
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 7 článkům s kontrolou a certifikací a ještě navíc ušetříš 12 Kč. Nabídka je omezená pouze pro první články z kurzu a obsahuje exkluzivní slevu 15%.
26 bodů získáš za přidání svého článku na síť nebo odpovídá 75 Kč 64 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.
Předchozí článek
Hledání nejkratší cesty v grafu
Všechny články v sekci
Grafové algoritmy
Aktivity (4)