Dijkstran algoritmi

Wikipedia
Loikkaa: valikkoon, hakuun
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.[1] Algoritmi toimii suunnatuilla graafeilla, joiden viivojen painot ovat ei-negatiivisia. Algoritmia käytetään muun muassa tietoliikenneverkkojen reitityksessä.

Algoritmin selitys[muokkaa | muokkaa wikitekstiä]

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) \ge 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[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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

Lähteet[muokkaa | muokkaa wikitekstiä]

  1. Philip L. Frana, Thomas J. Misa: An interview with Edsger W. Dijkstra. Communications of the ACM, 8/2010, 53. vsk, nro 8, s. 41-47. New York: ACM. doi:10.1145/1787234.1787249. (englanniksi)

Kirjallisuutta[muokkaa | muokkaa wikitekstiä]

Commons
Wikimedia Commonsissa on kuvia tai muita tiedostoja aiheesta Dijkstran algoritmi.
  • 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.
  • Keijo Ruohonen: Graafiteoria (2004)
    • Yliopistotason opintomoniste graafiteoriaan