Dijkstra algoritm

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

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. Algoritmi võib kasutada ka leidamaks lühimat teed üksnes kahe tipu vahel. Seda algoritmi kasutatakse tihti marsruutimisel. Dijkstra algoritm on ahne algoritm.

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

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

Omistame $d[a]\gets 0,\ p[a]\gets a$

Kõigi tippude jaoks $u\in V$ välja arvatud $a$

omistame algväärtused $d[u]\gets \infty$

Kuni $\exists v\notin U$

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

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

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

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

muudame $p[u]\gets p[v],u$

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 ning m servade arv.

Vaata ka

• Floydi-Warshalli algoritm
• Bellmani-Fordi algoritm
• 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