Dijkstrov algoritem

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search

Dijkstrov algoritem ali drevo najkrajših poti se uporablja za iskanje drevesa najkrajših poti. Dijkstra je razvil algoritem za drevo najkrajših poti s 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 ena točka (vozlišče), v ali u, že v drevesu T.

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

Pri drevesu najkrajših poti imamo usmerjeni graf.

Zahtevnost[uredi | uredi kodo]

Časovna zahtevnost algoritma je Θ(n2), ker mora algoritem preveriti vsako povezavo najmanj enkrat, teh povezav pa je v grafu z n točkami n*(n-1) saj gre za polni graf.

Splošna procedura[uredi | uredi kodo]

1. V drevesu T še ni nobene točke, zato je podatek oče[i] za vse točke enak 0.
2. V drevo T dodam začetno točko.
   oče[začetna točka] = 0
   razdalja[začetna_točka] = 0, torej razdalja od začetne do začetne točke je 0
   zadnje vstavljena točka je začetna točka
3. Pojdi čez vse točke, ki še niso v drevesu, torej skozi vse točke razen začetne točke in določi točko, 
   ki je najbližje začetni točki neposredno in jo vključi v rešitev in sicer:
   oče[u] = začetna točka
   zadnje vstavljena točka je u
   osvežim razdalje
   Za tiste točke, ki še niso v drevesu, določimo razdaljo do začetne točke tako, 
   da vzamemo minimum med razdaljo na prejšnjem koraku, izračunano razdaljo od te točke
   preko točk, ki so že v drevesu ter razdaljo med začetno točko in točkami, 
   ki so v listih drevesa n. Jim prištejemo še pot iz točke, ki je list, do trenutno obravnavane točke.
4. Ponavljaj tretji korak, dokler niso vse točke v drevesu

Zunanje povezave[uredi | uredi kodo]