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 formula_1 ja lähtöpisteen formula_2. Funktiolla formula_3 kuvataan kahden pisteen formula_4 ja formula_5 välistä painoa mikäli viiva on olemassa. Graafista oletetaan että viivojen painot ovat ei-negatiivisia (formula_6). formula_7 kuvaa graafin kaikkien pisteiden joukkoa.
Algoritmi etsii lyhyimmän polun pisteestä formula_2 kaikkiin muihin pisteisiin. Aluksi merkitään lyhin tunnettu polku pisteestä formula_2 itseensä nollaksi, ja etäisyydet pisteestä formula_2 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 formula_2 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ä formula_2, koska siihen tunnetaan triviaalisti lyhyin polku. Seuraavalla kierroksella aloitetaan pisteestä formula_4 joka on pisteen formula_2 lähin naapuri. Voidaan osoittaa että mikään kiertopolku ei tuota lyhyempää polkua pisteeseen formula_4, 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)
 11 for each edge (u,v) outgoing from u
 12 do if d[v] &gt; 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 formula_16) saadaan algoritmin kokonaisvaativuudeksi formula_17.
Algoritmi voidaan toteuttaa kekoa käyttäen siten että sen kokonaisvaativuudeksi saadaan formula_18. Vieläkin suorituskykyisempi toteutus saadaan käyttäen Fibonacci-kekoa jolloin vaativuudeksi saadaan formula_19. Kummassakin tapauksessa kekoa täytyy päivittää aina kun tehdään sijoitus d[v] := d[u] + w(u,v).