Dijkstrin algoritam
Dajkstrin algoritam je jedan od algoritama za nalaženje najkraćeg puta u grafu sa nenegativnim težinama ivica. Ime je dobio po holandskom informatičaru Edsheru Dajkstri.
Neka je dat težinski usmereni graf G i početni čvor s iz G. Ako skup svih čvorova grafa obeležimo sa V, skup ivica sa E, tada je svaka ivica iz E, predstavljena parom čvorova (u,v) koje ona povezuje iz V. Takođe, neka svaka ivica dobije određenu vrednost (težinu) w. Težina svake ivice se može predstaviti kao rastojanje između dva čvora koje ona povezuje. Dužina puta između dva čvora je suma težina ivica na tom putu. Za dati par čvorova s i t iz V, Dajkstrin algoritam nalazi vrednost najkraćeg puta. Česta je njegova upotreba za nalaženje najkraćeg puta od čvora s do svih ostalih iz skupa V.
Opis algoritma[uredi | uredi kod]
Dajkstrin algoritam je pohlepni algoritam koji se zasniva na pamćenju vrednosti d[v] trenutnog najkraćeg puta od s za svaki čvor v. Za početni čvor ta vrednost najpre iznosi 0, tj. d[s]=0, a za ostale čvorove se uzima vrednost beskonačno. Pri prestanku rada algoritma, d[v] dobija vrednost najkraćeg puta iz s u v, ili vrednost beskonačno, ukoliko takav put ne postoji.
Osnovna operacija Dajkstrinog algoritma je oslobađanje ivica: ukoliko postoji ivica iz u ka v, tada trenutno najkraći put iz s u u (d[u]) može dobiti vrednost sume d[v] i težine ivice (u, v). Dakle, njegova dužina će iznositi d[u]+w(u, v), ukoliko je ova vrednost manja od d[v]. Proces oslobađanja ivica se nastavlja se dok vrednost d[v] ne određuje najkraći put iz s u v, za svaki čvor v.
Tokom izvršavanja algoritma izdvajaju se dva skupa čvorova S i Q. U skupu S su oni čvorovi za koje je poznata vrednost d[v], a u skupu Q svi ostali. Na početku je skup S prazan, a u svakoj iteraciji jedan čvor se premešta iz Q u S. To je onaj čvor koji ima najmanju vrednost d[u]. Na kraju se oslobađaju sve ivice (u,v) gore opisanim postupkom.
Pseudokod[uredi | uredi kod]
U sledećem pseudokodu, u := Extract_Min(Q) nalazi čvor u iz skupa Q koji ima najmanju vrednost d[u]. Taj čvor se izbacuje iz skupa Q.
1 function Dijkstra(G, w, s)
2 for each vertex v in V[G] // Inicijalizacija
3 d[v] := infinity
4 previous[v] := undefined
5 d[s] := 0
6 S := empty set
7 Q := V[G]
8 while Q is not an empty set // Dajkstrin algoritam
9 u := Extract_Min(Q)
10 S := S union {u}
11 for each edge (u,v) outgoing from u
12 if d[u] + w(u,v) < d[v] // Oslobađanje ivice (u,v)
13 d[v] := d[u] + w(u,v)
14 Q := Q union {v}
15 previous[v] := u
Ako nas interesuje samo najkraći put između s i t, pretragu možemo prekinuti u redu 9 ako je u = t.
Sada, jednostavno možemo odrediti najkraći put iz s do t:
1 S := empty sequence 2 u := t 3 while defined previous[u] 4 insert u to the beginning of S 5 u := previous[u]
U skupu S ke sadržana lista čvorova koji se nalaze na najkraćem putu iz s u t. Ukoliko taj put ne postoji, skup S je prazan.
Vremenska složenost[uredi | uredi kod]
Vremenska složenost Dajkstrinog algoritma nad grafom sa ivicama E i čvorovima V se može izraziti u zavisnosti od |E| i |V|.
Kod jednostavne implementacije čvorovi iz skupa Q su sadržani u nizu, a operacija Extract-Min(Q) zahteva samo linearnu pretragu za sve čvorove iz skupa Q. U tom slučaju, vremenska složenost iznosi O(V2).
Efikasnije je implementirati Dajsktrin algoritam koristeći binarni hip. Tada je vremenska složenost O((E+V)logV).
