Brži algoritam najkraćeg puta
Brži algoritam najkraćeg puta (BANP) predstavlja poboljšanje Bellman–Ford algoritma koji računa najkraće puteve sa jednim izvorom u usmerenom težinskom grafu. Algoritam radi dobro na nasumičnim proređenim grafovima i posebno je pogodan za grafove koji sadrže grane sa negativnim težinama. Algoritam BANP je objavio 1994. godine Fanding Duan.
Algoritam[уреди | уреди извор]
Za zadati usmereni težinski graf G = (V, E) i izvorni čvor s, BANP algoritam pronalazi najkraći put od s do svakog čvora v u grafu. Dužina najkraćeg puta od s do v se čuva u d(v) za svaki čvor v.
Osnovna ideja BANP algoritma ista je kao i Bellman–Ford algoritam po tome što svaki čvor se koristi kao kandidat da relaksira susedne čvorove. Poboljšanje u odnosu na ostale je u tome što umesto da pokušava za sve čvorove slepo, BANP održava red čvorova kandidata i dodaje čvor u red samo ako je taj čvor relaksiran. Ovaj proces se ponavlja dok god nema više čvorova koji mogu biti relaksirani.
Ispod je pseudo-kod ovog algoritma. Ovde Q predstavlja red čvorova kandidata, i w(u, v) je težina grane (u, v).
procedure Shortest-Path-Faster-Algorithm(G, s) 1 for each vertex v ≠ s in V(G) 2 d(v) := ∞ 3 d(s) := 0 4 push s into Q 5 while Q is not empty 6 u := pop Q 7 for each edge (u, v) in E(G) 8 if d(u) + w(u, v) < d(v) then 9 d(v) := d(u) + w(u, v) 10 if v is not in Q then 11 push v into Q
Algoritam se takođe može primeniti na neusmereni graf tako što se zameni svaka neusmerena grana sa dve usmerene grane suprotnih smerova.
Prosečni slučaj algoritma[уреди | уреди извор]
Za nasumični graf, empirijska prosečna vremenska složenost je O(|E|).
Najgori slučaj algoritma[уреди | уреди извор]
Pretpostavimo da neko želi da pronađe najkraći put od čvora 1 do čvora n. Tada možemo dodati granu (i, i + 1) sa nasumičnom malom težinom za 1 ≤ i < n (tako da bi najkraći put trebao biti 1-2-...-n), i nasumično dodamo 4n drugih teških grana. U ovom slučaju, takozvani BANP algoritam će biti vrlo spor.
Tehnike optimizacije[уреди | уреди извор]
Performanse algoritma su strogo određene redosledom kojim čvorovi kandidati se koriste da relaksiraju ostale čvorove. U principu, ako je Q red sa prioritetom, onda algoritam zaista liči na Dijkstrin. Međutim, pošto se ovde ne koristi red sa prioritetom, dve tehnike se nekad koriste da unaprede kvalitet reda, što unapređuje i uspešnost prosečnog slučaja (ali ne i uspešnost najgoreg slučaja). Obe tehnike preuređuju redosled elemenata u Q tako da su čvorovi bliži izvoru prvi procesuirani. Stoga, kada se implementiraju ove tehnike, Q više nije FIFO red, već normalna dvostruka lista.
Male Oznake Prvo (MOP) tehnika. Pseudo-kod:
procedure Small-Label-First(G, Q) if d(back(Q)) < d(front(Q)) then u := pop back of Q push u into front of Q
Velike Oznake Zadnje (VOZ) tehnika. Pseudo-kod:
procedure Large-Label-Last(G, Q) x := average of d(v) for all v in Q while d(front(Q)) > x u := pop front of Q push u to back of Q