Dijkstra algoritm

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

Dijkstra algoritm on Edsger Wybe Dijkstra poolt 1959. aastal avaldatud[1] 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.

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.[2][3]

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

Algoritm[muuda | redigeeri lähteteksti]

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[muuda | redigeeri lähteteksti]

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[muuda | redigeeri lähteteksti]

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.[5]

Rakendusi[muuda | redigeeri lähteteksti]

Dijkstra algoritmi kasutatakse GIS rakenduse ArcView moodulis Network Analyst leidmaks kahe punkti vahelist optimaalseimat teed.[6]

Vaata ka[muuda | redigeeri lähteteksti]

Viited[muuda | redigeeri lähteteksti]

Välislingid[muuda | redigeeri lähteteksti]