Dijkstrův algoritmus

Dijkstrův algoritmus řeší problém nejkratších cest z kořene s (startovací vrchol, ze kterého začínáme) do ostatních vrcholů grafu pro grafy s nezáporným ohodnocením hran. Označíme si výchozí uzel, ze kterého budeme plánovat cestu. Dijsktrův algoritmus je založen na tom, že na začátku přiřadíme uzlům určité hodnoty a postupně jej budeme vylepšovat. Algoritmus si popíšeme ve slovním pseudokódu:

1. Ke každému uzlu přiřaď aktuální vzdálenost od počátečního uzlu. V případě samotného výchozího uzlu je vzdálenost 0, v případě ostatních uzlů je to nyní nekonečno.
2. Označ všechny uzly jako nenavštívené. Označ výchozí uzel jako aktuální uzel. Vytvoř množinu nenavštívených uzlů, která bude obsahovat všechny uzly kromě výchozího. Nyní se dostáváme k třetímu bodu, který se bude opakovat ve smyčce.
3. Podívej se na všechny nenavštívené sousedy aktuálního uzlu a vypočítej jejich vzdálenost od počátečního uzlu. Pokud má např. aktuální uzel vzdálenost 3 a délka hrany mezi tímto uzlem a jeho sousedem je 2, potom vzdálenost k tomuto sousedovi bude 3 + 2 = 5. Pokud je aktuální vzdálenost menší než dříve zaznamenaná vzdálenost tohoto souseda, pak ji přepiš lepší, kratší hodnotou. Poznamenejme, že i když jsme se na sousední uzly aktuálního uzlu podívali, stále zůstávají v množině nenavštívených.
4. Jakmile jsme se podívali na sousedy aktuálního uzlu, budeme považovat tento aktuální uzel za navštívený a vyjmeme ho z množiny nenavštívených uzlů. K tomuto uzlu už se nikdy nevrátíme.
5. Pokud byla cílová destinace označena jako navštívená, nebo nejmenší aktuální vzdálenost mezi uzly v množině nenavštívených uzlů je nekonečno, ukonči algoritmus.
6. Vyber uzel z množiny nenavštívených uzlů, který má nejmenší aktuální vzdálenost od výchozího uzlu, nastav jej jako „aktuální“ uzel a vrať se k bodu 3.

Pokud Vám pseudokód připomíná algoritmus procházení do šířky, není tomu tak náhodou. Dijsktrův algoritmus je skutečně rozšířením procházení grafu do šířky, přičemž místo datové struktury fronta zde využíváme podobného nástroje, kterým je prioritní fronta. Prioritní fronta funguje jako fronta, ve které mohou předbíhat uzly s nejkratší aktuální vzdáleností od zdroje.

Algoritmus tedy systematicky postupuje od výchozího uzlu k cílové destinaci a aktualizuje vzdálenosti. Výstupem algoritmu je pak délka nejkratší cesty z výchozího uzlu do všech ostatních uzlů.

Příklad: Vyhledejte nejkratší cestu z počátečního uzlu A do všech ostatních uzlů ohodnoceného grafu.