Flojd-Voršalov algoritam

U računarstvu Flojd-Voršalov algoritam algoritam (ponekad se zove i Roy-Floyd algoritam ili WFI algoritam, otkad je Bernard Roy opisao algoritam 1959) je algoritam analize grafova za nalaženje najkraćih putanja u težinskom, usmerenom grafu. Jedno izvršenje algoritma će naći najkraće putanje između svih parova čvorova. Floyd-Warshall algoritam je primer dinamičkog programiranja.

Opis algoritma[uredi | uredi izvor]

Flojd-Voršalov algoritam upoređuje sve moguće puteve u grafu između svakog para čvorova. On je u stanju da uradi to sa samo V3 poređenja (to je izuzetno obzirom da u grafu može biti V2 grana a svaka grana se proverava). Algoritam to radi tako što postepeno poboljšava procenu najkraćeg puta između dva čvora, dok ne bude poznato da je procena optimalna.

Neka je dat graf G sa čvorovima V, označenim od 1 do N. Dalje, neka postoji funkcija najkraciPut(i, ј,k) koja vraća najkraći mogući put od i do j koristeći samo čvorove od 1 do k kao međutačke na putu. Sada, koristeći ovu funkciju, cilj je naći najkraći put od svakog i do svakog j koristeći samo čvorove od 1 do k+1. Postoje dva kandidata za ovaj put: ili pravi najkraći put koristi samo čvorove iz skupa (1...k); ili postoji neki put koji ide od i do k+1, zatim od k+1 do j koji je bolji. Zna se da je najbolji put od i do j, koji koristi samo čvorove od 1 do k, definisan funkcijom najkraciPut(i, ј,k), i očito je da kad bi postojao bolji put od i do k+1 do j, dužina ovog puta bi bila konkatenacija najkraćeg puta od i do k+1 (koristeći čvorove u (1...k)) i najkraćeg puta od k+1 do j (takođe koristeći čvorove u (1...k)).

Dakle, može se definisati najkraciPut(i, ј,k) preko rekurentne formule: ${\textrm {najkraciPut}}(i,j,k)=\min({\textrm {najkraciPut}}(i,j,k-1),{\textrm {najkraciPut}}(i,k,k-1)\,+\,{\textrm {najkraciPut}}(k,j,k-1));\,\!$

${\textrm {najkraciPut}}(i,j,0)={\textrm {edgeCost}}(i,j);\,\!$

Ova formula je srž Flojd Voršal-a. Algoritam radi tako što prvo izračuna najkraciPut(i, ј,1) za sve (i,j) parove, zatim koristeći to nalazi najkraciPut(i,j,2) za sve parove (i,j), itd. Ovaj proces se nastavlja dok se ne stekne uslov k=n. I, nađen je najkraći put za sve (i,j) parove koristeći potrebne međučvorove.

Pseudokod[uredi | uredi izvor]

Kada se izračunava k-ti slučaj zgodno je što se može snimiti proračun preko informacije sačuvane od izračunavanja slučaja k-1. To znači da algoritam koristi kvadratnu memoriju. Obratiti pažnju i uočiti početne uslove:

1 /* Podrazumeva se da postoji funkcija edgeCost(i,j,k) koja vraća  cenu od i do j
2    (beskonačnost ako je nema).
3    Takođe se podrazumeva da je n broj čvorova i edgeCost(n,n)=0
4 */
5
6 int path[][];
7 /* A .- matrica dimenzije 2. U svakom koraku algoritma, path[i][j] je najkraći put
8    od i do j koristeći međuvrednosti u (1..k-1).  Svaki path[i][j] je inicijalizovan na
9    edgeCost(i,j).
10 */
11
12 procedure FloydWarshall ()
13    for k: = 0 to n − 1
14    begin
15       for each (i,j) in (0..n − 1)
16       begin
17          path[i][j] = min (path[i][j], path[i][k]+path[k][j] );
18       end
19    end
20 endproc

Ponašanje sa negativnim ciklusima[uredi | uredi izvor]

Za numerički validan izlaz, Flojd-Voršalov algoritam pretpostavlja da nema negativnih ciklusa (u stvari, između bilo kog para čvorova koje čine negativni ciklus najkraći put nije dobro definisan zato što put može biti beskonačno mali). Ipak, ako postoje negativni ciklusi, Flojd-Voršalov algoritam se može iskoristiti da se oni otkriju. Ako se izvrši algoritam još jednom, neke putanje se mogu skratiti ali ne postoji garancija da će se između svih čvorova, između kojih putevi mogu biti beskonačno mali, skratiti put. Ako je broj u dijagonali matrice puta negativan, to je dovoljan je i neophodan uslov da dati čvor pripada negativnom ciklusu.

Vremenska složenost i Analiza[uredi | uredi izvor]

Da bi našli svih ${\mathit {n}}^{2}$ od ${\mathcal {W}}_{k}$ od onih ${\mathcal {W}}_{\mathit {k-1}}$ potrebno je $2{\mathit {n}}^{2}$ operacija nad bitovima. Kako se počinje sa ${\mathcal {W}}_{0}={\mathcal {W}}_{\mathcal {R}}$ i računa niz od n „zero-one“ (matrica čiji su svi elementi ili 0 ili 1) matrica ${\mathcal {W}}_{1}$ , ${\mathcal {W}}_{2}$ , $...$ , ${\mathcal {W}}_{\mathit {n}}={\mathcal {M}}_{{\mathcal {R}}^{*}}$ , ukupan broj operacija nad bitovima je ${\mathit {n}}\times 2{\mathit {n}}^{2}=2{\mathit {n}}^{3}$ . Složenost algoritma je $\Theta (n^{3})$ i može da se reši determinističkom mašinom u polinomijalnom vremenu.

Ako se sa |V| označi broj čvorova grafa, tada je vremenska složenost tačno O(|V|³).

Primene i generalizacije[uredi | uredi izvor]

Flojd-Voršalov algoritam, između ostalog, može biti korišten u rešavanju sledećih problema:

Najkraći putevi u usmerenim grafovima (Flojdov algoritam).
Tranzitivno zatvorenje u usmerenim grafovima (Voršalov algoritam). U Voršalovoj prvobitnoj formulaciji algoritma, graf je beztežinski i reprezentovan je Bulovskom matricom. Zatim je operacija sabiranja zamenjena logičkom konjukcijom (AND) i operacija minimuma logičkom disjunkcijom (PR).
Za nalaženje regularnog izraza koji opisuje regularni jezik prihvaćen konačnim automatom (Klinijev algoritam).
Inverzija realnih matrica (Gaus-Žordanov algoritam).
Optimalno rutiranje. Kod ove primene interesuje nas nalaženje puta sa maksimalnim protokom između dva čvora. To znači da umesto minimum u gornjem pseudokodu mi uzimamo maksimum. Težine grana predstavljaju fiksirane prepreke za protok. Težine puteva predstavljaju zagušenja; zato se gornja operacija sabiranja zamenjuje operacijom minimuma.
Provera bipartitnosti neusmerenog grafa.

Spoljašnje veze[uredi | uredi izvor]