Dijkstrov algoritem

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

Časovna zahtevnost algoritma je Θ(n²), 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

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