Brži algoritam najkraćeg puta

Из Википедије, слободне енциклопедије
Jump to navigation Jump to search

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 vs 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.

Dokaz korektnosti[уреди]

http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm

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 (ii + 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