|
|
ALGORITMUL LUI FLOYD
Se considera un graf orientat G=(N,A), in care fiecare arc a=(i,j) din A are o pondere pozitiva COST[i,j]. Problema drumurilor minime corespunzatoare tuturor perechilor de noduri presupune determinarea, pentru fiecare pereche ordonata (i,j), a lungmii drumului minim care conecteaza i cu j.
O rezolvare a acestei probleme este aplicarea repetata a algoritmului lui Dijkstra avand ca nod origine fiecare nod al grafului.
O alta metoda de rezolvare directa a acestei probleme este data de algoritmul lui Floyd.
Algoritmul utilizeaza o matrice A de dimensiuni NxN, in care A[i,j] va fi lungimea drumului minim de la i la j. Initial, se presupune ca drumul minim de la i la j este arcul (i,j). Se testeaza apoi fiecare nod k al grafului, pentru a vedea daca pentru fiecare pereche de noduri i,j nu exista un drum mai scurt de la i la j trecand prin k (figura 1), adica daca suma drumurilor minime de la i la k si de la k la j nu este mai mica decat drumul considerat minim de la i la j. Pentru a determina traseele drumurilor minime, se poate introduce o matrice Drum de dimeniune NxN, Drum[i,j] memoreaza acel nod k care conduce in cadrul algoritmului la scurtarea drumului A[i,j]. Se va alege o valoare speciala pentru "nod inexistent". Daca Drum[i,j]=nod inexistent, atunci cel mai scurt drum de la i la j este arcul direct.
procedure Floyd;
{Date de intrare: Graful orientat ponderat G=(N,A)}
{Date de iesire: pentru fiecare pereche de noduri i,j se
calculeaza A[i,j]=lungimea drumului minim de la i la j,
si Drum[i,j]=un nod intermediar pe traseu de la i la j}
begin
* initializeaza matricea lungimilor drumurilor minime
A[i,j]) si matricea nodurilor intermediare de
pe trasee (Drum[i,j]) presupunand ca drumul minim
intre oricare doua noduri este arcul direct
for * fiecare nod k al grafului do
for * fiecare pereche de noduri i,j do
if (* suma drumurilor de la i la k si de la k
la j e mai mica decat drumul de la i la j
( A[i,k] + A[k,j] < A[i,j] )) then
begin
* actualizeaza valoarea drumului minim,
prin A[i,j] := A[i,k] + A[k,j]
* memoreaza punctul de pe traseu, Drum[i,j]:= k
end
end; {Floyd}
Pentru reconstituirea traseelor, se poate folosi urmatorul algoritm recursiv.
Algoritmul afiseaza traseul drumului minim intre intre doua noduri specificate,
nodurile i si j.
procedure Traseu(i,j:integer);
{Date de intrare: nodurile i si j si matricea Drum calculata
de algoritmul lui Floyd}
{Date de iesire: afiseaza in ordine nodurile intermediare de
pe traseul drumului minim de la i la j}
begin
if (*este cel putin un nod k=Drum[i,j]
intermediar i la j) then
begin
Traseu(i,k);
writeln(k);
Traseu(k,j);
end;
end; { Traseu }
Timpul de executie al algoritmului lui Floyd este de ordinul O(n3).
In timp ce versiunea algoritmului lui Dijkstra determina drumurile minime cu origine comuna in O(n2) in cazul grafurilor dense implementate prin matrici de adiacente, deci aplicarea de n ori a procedurii Dijkstra duce la o performanta O(n3),in cazul grafurilor rare reprezentate prin liste de adiacenta, algoritmul lui Dijkstra este de ordinul O(a log n), deci aflarea tuturor drumurilor minime se poate face cu o performanta O(a n log n).
|
