Dijkstrov algoritem
From Wikipedia, the free encyclopedia
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.