Dijkstrov algoritem/NaceMikus

Iz MaFiRaWiki

Dijkstrin algoritem je algoritem, ki po požrešni metodi rešuje problem drevesa najkrajših poti(SSSP, single-source shortest paths). To je vpeto drevo, ki vsebuje vse najkrajše poti od nekega izbranega vozlišča do vseh ostalih vozlišč.

Formalno: algoritmu podamo vpet graf G in izbrano vozlišče v iz G. V naj bo množica vseh vozlišč v grafu G. Povezave med vozlišči pa naj bojo pari (a,b), kar naj predstavlja povezavo med vozliščem a in b (če gre za usmerjen graf, so pari urejeni). Množica vseh povezav je E. Definiramo funckijo uteži w: E → [0, ∞), ki povezavi priredi utež, ki v posebnem lahko predstavlja ceno, razdaljo itd.

Algoritem

Začnemo z izbranim vozliščem s. Algoritem deluje tako, da si za vsako vozlišče v zapomne ceno d[v] najcenejše poti do izbranega vozlišča s. Na začetku je ta cena 0 za vozlišče s in ∞ za vse ostale. Ko algoritem opravi prvi korak, bo na vseh vozliščih, ki so z vozliščem s povezani, d[v] kar cena povezave med v in s. Izbere se najcenejšo, npr. povezava od s do s1, in se gleda vozlišča, ki so neposredno povezana s tem vozliščem. d[v] teh vozlišč je torej vsota cene povezave (s,s1) in cene povezave (s1,v). Algoritem zdaj od vseh d[v] izbere najcenejšo in postopek nadaljuje, dokler ne pride do zadnjega vozlišča.


Glej tudi

Osebna orodja