Dijkstran algoritmi

Dijkstran algoritmi selvittää lyhyimmän mahdollisen polun pisteiden a ja b välillä.

Dijkstran algoritmi on Edsger Dijkstran kehittämä, vuonna 1959 julkaistu algoritmi, joka etsii graafille lyhyimmän polun yhdestä pisteestä kaikkiin muihin pisteisiin. Algoritmi toimii suunnatuilla graafeilla, joiden särmien painot ovat ei-negatiivisia. Algoritmia käytetään muun muassa tietoliikenneverkkojen reitityksessä.

Algoritmin selitys

Algoritmi tarvitsee lähtötiedoiksi graafin $G$ ja lähtöpisteen $s$. Funktiolla $w(u,v)$ kuvataan kahden pisteen $u$ ja $v$ välistä painoa mikäli viiva on olemassa. Graafista oletetaan että viivojen painot ovat ei-negatiivisia ($w(u,v)\geq 0$). $V[G]$ kuvaa graafin kaikkien pisteiden joukkoa.

Algoritmi etsii lyhyimmän polun pisteestä $s$ kaikkiin muihin pisteisiin. Aluksi merkitään lyhin tunnettu polku pisteestä $s$ itseensä nollaksi, ja etäisyydet pisteestä $s$ muihin pisteisiin äärettömäksi. Tämän jälkeen käydään graafia läpi kierroksittain. Jokaisella kierroksella pyritään etsimään uusi polku pisteeseen $s$ joka on lyhyempi kuin jokin aikaisemmin tunnettu. Erityisesti jokaisella kierroksella aloitetaan tarkastelemaan jotain sellaista pistettä johon jo tunnetaan lyhin mahdollinen polku. Kun kyseisestä pisteestä aloitetaan uusi kierros, ei siitä pisteestä enää aloiteta millään myöhemmällä kierroksella. Ensimmäisellä kierroksella aloitetaan pisteestä $s$, koska siihen tunnetaan triviaalisti lyhyin polku. Seuraavalla kierroksella aloitetaan pisteestä $u$ joka on pisteen $s$ lähin naapuri. Voidaan osoittaa että mikään kiertopolku ei tuota lyhyempää polkua pisteeseen $u$, koska kaikki viivojen painot ovat ei-negatiivisia, ja jolla on käsittelemättömien pisteiden joukossa pienin polkupituus.

Pseudokoodi

Oheisessa algoritmissa u := Extract-Min(Q) etsii ja palauttaa sellaisen pisteen u pistejoukosta Q, jolla on pienin mahdollinen arvo d[u]. Piste u ei ole välttämättä yksikäsitteinen. Tämän lisäksi Extract-Min funktio poistaa pisteen u joukosta Q.

1   function Dijkstra(G, w, s)
2      for each vertex v in V[G]      // Alustetaan etäisyydet
3         do d[v] := infinity
4            previous[v] := undefined
5      d[s] := 0                      // Alkupisteen matka = 0
6      S := empty set                 // Käsiteltyjen pisteiden joukko
7      Q := set of all vertices       // Kaikki pisteet jonoon
8      while Q is not an empty set
9         do u := Extract-Min(Q)
10           S := S union {u}
11           for each edge (u,v) outgoing from u
12              do if d[v] > d[u] + w(u,v)
13                 then d[v] := d[u] + w(u,v)    // Lyhyempi reitti
14                      previous[v] := u

Jos algoritmin tuloksessa kiinnostaa vain lyhyin polku pisteiden s ja t välillä, voi rivillä 9 lopettaa etsinnän mikäli u = t.

Lyhyin polku pisteiden s ja t välillä määritetään seuraavalla koodilla. Koodi muodostaa jonon S pisteistä jotka muodostavat lyhimmän polun tarkasteltujen pisteiden välille.

1 S := empty sequence 
2 u := t
3 while defined u                                        
4    do insert u to the beginning of S
5       u := previous[u]

Laskennallinen vaativuus

Dijkstran algoritmin laskennallinen vaativuus riippuu sen toteutustekniikasta. Suorituskyvyn suhteen avainasemassa ovat funktio Extract-Min ja sijoitus d[v] := d[u] + w(u,v).

Mikäli Extract-Min funktio toteutetaan yksinkertaisella listan läpikäymisellä (vaativuus $O(V)$) saadaan algoritmin kokonaisvaativuudeksi $O(V^{2})$.

Algoritmi voidaan toteuttaa kekoa käyttäen siten että sen kokonaisvaativuudeksi saadaan $O((E+V)\;\log(V))$. Vieläkin suorituskykyisempi toteutus saadaan käyttäen Fibonacci-kekoa jolloin vaativuudeksi saadaan $O(V\log(V)+E)$. Kummassakin tapauksessa kekoa täytyy päivittää aina kun tehdään sijoitus d[v] := d[u] + w(u,v).

Kirjallisuutta

• Cormen, T. H.; Leiserson C. E.; & Rivest R. L. (1990) Introduction to Algorithms. MIT Press. ISBN 0-262-03141-8
  • Perusteos tietojenkäsittelyn algoritmeista. Tämän artikkelin pseudokoodi on alun perin mukailtu tästä kirjasta.

Aiheesta muualla

• Ruohonen, Keijo: Graafiteoria (PDF) (Tampereen teknillisen yliopiston opintomoniste) math.tut.fi. 2013. Arkistoitu 30.12.2020.