Dijkstrův algoritmus

Dijkstrův algoritmus je algoritmus sloužící k nalezení nejkratší cesty v ohodnoceném grafu. Je konečný (pro jakýkoliv konečný vstup algoritmus skončí), protože v každém průchodu cyklu se do množiny navštívených uzlů přidá právě jeden uzel, průchodů cyklem je tedy nejvýše tolik, kolik má graf vrcholů. Funguje nad hranově kladně ohodnoceným grafem (neohodnocený graf lze však na ohodnocený snadno převést). Pro grafy s hranami se záporným ohodnocením se obvykle používá pomalejší Bellmanův–Fordův algoritmus.

Algoritmus poprvé popsal nizozemský informatik Edsger Dijkstra.

Popis algoritmu

Mějme graf ${\displaystyle G}$, v němž hledáme nejkratší cestu. Řekněme, že ${\displaystyle V}$ je množina všech vrcholů grafu ${\displaystyle G}$ a množina ${\displaystyle E}$ obsahuje všechny hrany grafu ${\displaystyle G}$. Algoritmus pracuje tak, že si pro každý vrchol ${\displaystyle v}$ z ${\displaystyle V}$ pamatuje délku nejkratší cesty, kterou se k němu dá dostat. Označme tuto hodnotu jako ${\displaystyle d[v]}$. Na začátku mají všechny vrcholy ${\displaystyle v}$ hodnotu ${\displaystyle d[v]=\infty }$, kromě počátečního vrcholu ${\displaystyle s}$, který má ${\displaystyle d[s]=0}$. Nekonečno symbolizuje, že neznáme cestu k vrcholu.

Dále si algoritmus udržuje množiny ${\displaystyle Z}$ a ${\displaystyle N}$, kde ${\displaystyle Z}$ obsahuje už navštívené vrcholy a ${\displaystyle N}$ dosud nenavštívené. Algoritmus pracuje v cyklu tak dlouho, dokud ${\displaystyle N}$ není prázdná. V každém průchodu cyklu se přidá jeden vrchol ${\displaystyle v_{min}}$ z ${\displaystyle N}$ do ${\displaystyle Z}$, a to takový, který má nejmenší hodnotu ${\displaystyle d[v]}$ ze všech vrcholů ${\displaystyle v}$ z ${\displaystyle N}$.

Pro každý vrchol ${\displaystyle u}$, do kterého vede hrana (označme její délku jako ${\displaystyle l(v_{min},u)}$) z ${\displaystyle v_{min}}$, se provede následující operace: pokud ${\displaystyle (d[v_{min}]+l(v_{min},u))<d[u]}$, pak do ${\displaystyle d[u]}$ přiřaď hodnotu ${\displaystyle d[v_{min}]+l(v_{min},u)}$, jinak neprováděj nic.

Když algoritmus skončí, pro každý vrchol ${\displaystyle v}$ z ${\displaystyle V}$ je délka jeho nejkratší cesty od počátečního vrcholu ${\displaystyle s}$ uložena v ${\displaystyle d[v]}$.

Pseudokód – Pascal

 1  function Dijkstra(E, V, s):
 2     for each vertex v in V:           // Inicializace
 3         d[v] := infinity              // Zatím neznámá vzdálenost z počátku s do vrcholu v
 4         p[v] := undefined             // Předchozí vrchol na nejkratší cestě z počátku s k cíli
 5     d[s] := 0                         // Vzdálenost z s do s
 6     N := V                            // Množina všech dosud nenavštívených vrcholů. Na začátku všech vrcholů.
 7     while N is not empty:             // Samotný algoritmus
 8         u := extract_min(N)           // Vezměme "nejlepší" vrchol                          
 9         for each neighbor v of u:
10             alt = d[u] + l(u, v)      // v 1. smyčce cyklu u je s d[u] = 0
11             if alt < d[v]              
12                 d[v] := alt
13                 p[v] := u

V případě, že nás zajímá pouze nejkratší cesta mezi zdrojovým a cílovým vrcholem, můžeme ukončit hledání na řádce 9 if u = target. Cestu ze zdroje do cíle pak zjistíme cyklem:

1 S := empty sequence 
2 u := target
3 while defined p[u]
4     insert u at the beginning of S
5     u := p[u]

Obecnější problém je nalezení nejkratších cest mezi zdrojovým vrcholem a všemi ostatními (případně nějakou jejich podmnožinou). V tomto případě je nutné v poli p[] ukládat všechny vrcholy splňující relaxační podmínku.

Efektivita algoritmu

Nejjednodušší implementace Dijkstrova algoritmu používá pro uložení prioritní fronty pole a operace Extract-Min(${\displaystyle Q}$) je lineární prohledávání všech vrcholů v ${\displaystyle Q}$. V tomto případě je asymptotická časová složitost ${\displaystyle O(|V|^{2}+|E|)}$, kde ${\displaystyle |V|}$ je počet vrcholů a ${\displaystyle |E|}$ počet hran.

Pro řídké grafy (grafy s počtem hran mnohem menším než ${\displaystyle |V|^{2}}$) může být Dijkstrův algoritmus implementován mnohem efektivněji tím, že se graf ukládá pomocí seznamu sousedů a funkce Extract-Min se implementuje pomocí binární nebo Fibonacciho haldy. Poté algoritmus běží v čase ${\displaystyle O((|E|+|V|)\log |V|)}$, Fibonacciho halda čas zlepší na ${\displaystyle O(|E|+|V|\log |V|)}$.

Literatura

• E. W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Sekce 24.3: Dijkstra's algorithm, pp.595–601.
• Jakub Černý: Nejkratší cesta v grafu, in: Základní grafové algoritmy (PDF)

Související články

• A*
• Bellmanův–Fordův algoritmus
• Floydův–Warshallův algoritmus

Externí odkazy

• Obrázky, zvuky či videa k tématu Dijkstrův algoritmus na Wikimedia Commons
• Nejkratší cesta v ohodnoceném grafu - popis Dijkstrova algoritmu
• Halda, Dijkstrův algoritmus