Dijkstrov algoritem

Iz Wikipedije, proste enciklopedije

Dijkstrov algoritem ali drevo najkrajših poti se uporablja za iskanje drevesa najkrajših poti. Dijkstra je razvil algoritem za drevo najkrajših poti z požrešno metodo. Drevo najkrajših poti gradimo korak za korakom. Naj bo T množica povezav, ki so že v drevesu. V drevo sprejmem novo povezavo e = (v,u) ∈ E in sicer tako, da naredim unijo T ∪ {e}. Da bo ta unija T ∪ {e} tudi drevo, mora biti natanko eno vozlišče, v ali u, že v drevesu T.

Predpostavimo, da je vozlišče v že v drevesu. Povezavo e = (v,u) lahko sprejmemo, če najkrajša pot od začetnega vozlišča do vozlišča u sme teči le po povezavah, ki so že v drevesu. Torej ne sme obstajati vozlišče w, ki ni v drevesu, takšno, da je pot iz izvora preko w do u krajša krajša kot po povezavah, ki že v drevesu. Da je pot od izvornega vozlišča do vozlišča u preko vozlišč, ki so v drevesu krajša, pa mora veljati, da so vsa vozlišča w (to so vozlišča, ki niso v drevesu) kvečjemu bolj oddaljena od izvora, kot je vozlišče u.

Pri drevesu najkrajših poti imamo usmerjen graf.

[uredi] Zahtevnost

Časovna zahtevnost algoritma je Θ(n²), ker mora algoritem preveriti vsako povezavo najmanj 1. krat, teh povezav pa je v grafu z n vozlišči n*(n-1) saj gre za polni graf.

[uredi] Splošna procedura

1. V drevesu T še ni nobenega vozlišča, zato je podatek oče[i] za vsa vozlišča enak 0.
2. V drevo T dodam začetno vozlišče.
   oče[začetno vozlišče] = 0
   razdalja[začetno_vozlišče] = 0, torej razdalja od začetnega do začetnega vozlišča je 0
   zadnje vstavljeno vozlišče je začetno vozlišče
3. Pojdi čez vse vozlišča, ki še niso v drevesu, torej skozi vsa vozlišča razen začetnega vozlišča in določi vozlišče, 
   ki je najbližje začetnemu vozlišču direktno in ga vključi v rešitev in sicer:
   oče[u] = začetno vozlišče
   zadnje vstavljeno vozlišče je u
   osvežim razdalje
   Za tista vozlišča, ki še niso v drevesu, določimo razdaljo do začetnega vozlišča tako, 
   da vzamemo minimum med razdaljo na prejšnjem koraku, izračunano razdaljo od tega vozlišča 
   preko vozlišč, ki so že v drevesu ter razdaljo med začetnim vozliščem in vozlišči, 
   ki so v listih drevesa n. Jim prištejemo še pot iz vozlišča, ki je list, do trenutno obravnavanega vozlišča.  
4. Ponavljaj tretji korak, dokler niso vsa vozlišča v drevesu