Dijkstra algoritm

Dijkstra algoritm on Edsger Dijkstra poolt 1959. aastal avaldatud^[1] graafi läbimise algoritm, mis leiab lühima tee kahe suvalise graafi tipu vahel. Seda algoritmi kasutatakse tihti marsruutimisel.

Algoritm leiab graafi etteantud algtipust vähima kaalutud pikkusega ahelad (ehk lühimad teed) algtipu ning kõigi teiste 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).

Algoritm

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

Omista igale tipule esialgsed kauguste väärtused. Määra algtipu kauguseks null ning kõigi ülejäänud tippude kauguseks lõpmatus.
Märgi kõik tipud külastamata tippudeks. Märgi algtipp valituks.
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 null ning kõigi teiste tippude esialge kaugus on lõpmatus), siis omista kaugusele uus väärtus.
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 ning selle tipu vähim kaugus.
Märgi külastamata tippudest valituks (algtipust) vähima kaugusega tipp. Ning pöördu tagasi 3. sammu juurde.

Vaata ka

Viited

↑ Edsger W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, nr. 1, 1959, lk 269–271

Välislingid

[harv-1] Edsger W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, nr. 1, 1959, lk 269–271

[1]