Dijkstra algoritm

Dijkstra algoritm on Edsger Wybe Dijkstra poolt 1959. aastal avaldatud graafi läbimise algoritm, mis leiab sidusas graafis lühimad teed algtipust kõigisse teistesse tippudesse. Seda algoritmi kasutatakse tihti marsruutimisel. Dijkstra algoritm on ahne algoritm.

Näide Dijkstra algoritmi rakendamisest leidmaks lühimat teed algtipust (a) lõpptippu (b)

Algoritm leiab graafi etteantud algtipust vähima kaalutud pikkusega ahelad (ehk lühimad teed) algtipu ja kõigi ülejäänud tippude vahel. Seda võib kasutada ka lühima tee leidmiseks kindlast algtipust kindlasse lõpptippu, peatades algoritmi, kui lühim tee lõpptippu on leitud. Näiteks, kui graafi tipud tähistavad linnu ja servade kaalud tähistavad kahe omavahel teega ühendatud linna vahelist vahemaad, siis saab Dijkstra algoritmi kasutades leida lühimad teekonnad reisi lähtelinnast kõigisse teistesse linnadesse. Lühima tee leidmise algoritmi kasutatakse laialdaselt võrgu marsruutimisprotokollides, tuntumaid neist on IS-IS ja OSPF (Open Shortest Path First).

Dijkstra algoritm töötab sidusas graafis. Kui graaf pole sidus, siis igast tipust igasse tippu teed ei eksisteerigi ja seda ei saa ka leida. Siiski saab mittesidusateski graafides kasutada Dijkstra algoritmi tippudevahelise lühima tee leidmiseks, kui see eksisteerib, samuti kontrollimiseks, kas ühest tipust teise tee üldse olemas on.

Dijkstra algoritmi saab rakendada mittenegatiivsete kaaludega graafis lühimate teede leidmiseks. Kui graafis on negatiivsed kaalud, siis tuleks kasutada kas Bellmanni-Fordi või Floydi-Warshalli algoritmi.

Mikkel Thorupi hinnangul on kõik hilisemad ainsa allikaga lühima tee ülesande (single-source shortest-path problem) teoreetilised uurimused tuginenud Dijkstra algoritmile.

Algoritm

Nimetagem algpunktiks valitud tippu algtipuks. Olgu tipu Y kauguseks tipu Y kaugus algtipust. Dijkstra algoritm omistab tippudele kauguste esialgsed väärtused ja püüab neid siis samm-sammult parandada.

1. Omista igale tipule esialgsed kauguste väärtused. Määra algtipu kauguseks 0 ja kõigi ülejäänud tippude kauguseks lõpmatus.
2. Märgi kõik tipud külastamata tippudeks. Märgi algtipp valituks.
3. Arvuta valitud tipu veel külastamata naabertippude kaugused (algtipust). Näiteks kui valitud tipu (A) kaugus on 6 ning seda tippu naabertipuga B ühendava serva pikkus on 2, siis on tipu B kaugus läbi tipu A 6+2=8. Kui see kaugus on väiksem kui varem välja arvutatud kaugus (algtipul 0 ja kõigil teistel tippudel lõpmatus), siis omista kaugusele uus väärtus.
4. Kui valitud tipu kõik naabertipud on üle kontrollitud, siis märgi valitud tipp külastatuks. Juba külastatud tippu enam ei kontrollita ning selle salvestatud kaugus on lõplik ja selle tipu vähim kaugus.
5. Märgi külastamata tippudest valituks (algtipust) vähima kaugusega tipp ja pöördu tagasi 3. sammu juurde. Kui külastamata tippe enam pole, on algoritmi töö läbi. Kui kõigi külastamata tippude kaugus on lõpmatus, siis on töö samuti läbi: neid ei saagi külastada.

Pseudokood

Järgnevas koodis on $d[v]$ tipu $v$ kaugus algtipust $a$, $p[v]$ on $v$-le eelnev tipp lühimal teel $a$-st ja $w[vu]$ serva $vu$ pikkus. $V$ tähistab graafi tippe ja $E$ graafi servasid. $U$ on külastamata tippude hulk.

Kõigi $v\in V$ kohta

$d[v]\gets \infty$

$U\gets V$ $d[a]\gets 0$

Kuni $U\neq \emptyset$

Olgu $v\in U$ minimaalse $d[v]$ -ga tipp

Kõigi $u\in U$ kohta, nii et $vu\in E$

kui $d[u]>d[v]+w[vu]$ siis

$d[u]\gets d[v]+w[vu]$

$p[u]\gets v$

$U\gets U\setminus \{v\}$

Keerukus

Keerukusteoreetilises mõttes on Dijkstra algoritmi kasutades lühima tee leidmine ühest tipust kindlasse lõpptippu ja ühest algtipust kõigisse ülejäänud tippudesse võrdse keerukusega: mõlema keerukus on O(n²). Kui tarvis on leida mitte ainult lõpptipu kaugus algtipust, vaid ka lühim tee selleni (missuguseid tippe lühim tee läbib), ei muuda seegi ülesannet keerukamaks.

Kasutades andmemassivina Fibonacci kuhja, on Dijksta algoritmi keerukus $O(n\log(n)+m)$, kus n on graafi tippude arv ja m servade arv.

Rakendusi

Dijkstra algoritmi kasutatakse GIS rakenduse ArcView moodulis Network Analyst, leidmaks kahe punkti vahelist optimaalset teed.

Vaata ka

• Laiuti otsing
• Sügavuti otsing
• Graafiteooria

Välislingid

• Intervjuu Edsger W. Dijkstraga, milles ta muuhulgas räägib Dijkstra algoritmi tekkeloost, Charles Babbage Institute University of Minnesota, Minneapolis, 2001. (inglise keeles)
• Java rakendus Dijkstra algoritmi näidete loomiseks