Dijkstran algoritmi
Wikipedia
Dijkstran algoritmi etsii graafille lyhyimmän polun yhdestä pisteestä kaikkiin muihin pisteisiin. Algoritmi toimii suunnatuilla graafeilla, joiden viivojen painot ovat ei-negatiivisia.
Sisällysluettelo |
[muokkaa] 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 (). 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.
[muokkaa] 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ä ole 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] // Initialization 3 do d[v] := infinity 4 previous[v] := undefined 5 d[s] := 0 6 S := empty set 7 Q := set of all vertices 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) // Relax (u,v) 13 then d[v] := d[u] + w(u,v) 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.
Algoritmin suorituksen jälkeen voi lyhyimmän polun pisteiden s ja t välillä määrittää seuraavasti:
1 S := empty sequence 2 u := t 3 while defined u 4 do insert u to the beginning of S 5 u := previous[u]
Nyt jono S on lista pisteistä mikä muodostaa lyhimmän reitin pisteestä s pisteeseen t.
[muokkaa] Laskennallinen vaativuus
Mikäli algoritmi toteutetaan tehokkaaasti, saadaan sen laskennalliseksi vaativuudeksi O((E + V) * log(V)), missä E on graafin viivojen määrä ja V on pisteiden määrä. Käytännössä tehokas toteutus käyttää Extract-Min funktiossa esimerkiksi prioriteettijonoa (vaativuus O(log(V))). Huonompi toteutus algoritmista voi käyttää Extract-Min funktion toteutukseen suoraviivaista listan läpikäymistä (vaativuus O(V)), ja tällöin algoritmin kokonaisvaativuudeksi tulee O(V2).
[muokkaa] 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.
- Keijo Ruohonen: Graafiteoria (2004)
- Yliopistotason opintomoniste graafiteoriaan