Dijkstran algoritmi

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  ja lähtöpisteen . Funktiolla  kuvataan kahden pisteen  ja  välistä painoa mikäli viiva on olemassa. Graafista oletetaan että viivojen painot ovat ei-negatiivisia ().  kuvaa graafin kaikkien pisteiden joukkoa.

Algoritmi etsii lyhyimmän polun pisteestä  kaikkiin muihin pisteisiin. Aluksi merkitään lyhin tunnettu polku pisteestä  itseensä nollaksi, ja etäisyydet pisteestä  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  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ä , koska siihen tunnetaan triviaalisti lyhyin polku. Seuraavalla kierroksella aloitetaan pisteestä  joka on pisteen  lähin naapuri. Voidaan osoittaa että mikään kiertopolku ei tuota lyhyempää polkua pisteeseen , 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          if do u == 0:
 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 ) saadaan algoritmin kokonaisvaativuudeksi .

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

Lähteet

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 

 

Algoritmit
Graafiteoria