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