Problema drumurilor minime corespunzătoare tuturor perechilor de noduri ("All-Pairs Shortest Path Problem") 

• Se presupune că există un graf orientat ponderat conţinând timpii de zbor pentru anumite trasee aeriene care conectează oraşe şi că se doreşte construcţia unei tabele care furnizează cei mai scurţi timpi de zbor între oricare două oraşe. 
• Aceasta este o instanţă a problemei drumurilor minime corespunzătoare tuturor perechilor de noduri (“all-pairs shortest paths problem”).  
• Pentru a formula problema în termeni formali, se presupune că se dă un graf orientat G=(N,A), în care fiecare arc (x,y) are o pondere pozitivă COST[x,y]. 
• Rezolvarea problemei drumurilor minime corespunzătoare tuturor perechilor de noduri pentru graful G, presupune determinarea pentru fiecare pereche ordonată de noduri (x,y),unde x,y Є N, a lungimii drumului minim care conectează nodul x cu nodul y.  
• Această problemă poate fi rezolvată cu ajutorul algoritmului lui Dijkstra, considerând pe rând, fiecare nod al grafului G drept origine.  
• De fapt rezultatul execuţiei algoritmului lui Dijkstra este un tablou care conţine distanţa de la origine la restul nodurilor grafului.  
• În cazul de faţă, deoarece este necesară determinarea distanţelor pentru toate perechile de noduri, avem nevoie de o matrice de elemente în care fiecare rând se poate determina în baza algoritmului lui Dijkstra.  
• rezolvare mai directă a problemei drumurilor minime corespunzătoare tuturor perechilor de noduri ale unui graf, este datorată algoritmului lui R.W. Floyd datând din anul 1962.

Algoritmul lui Floyd

• Fie graful ponderat G=(N,A)are are ataşată matricea de ponderi COST.  
• Pentru convenienţă, se consideră că nodurile mulţimii N sunt numerotate de la 1 la n. 
• Algoritmul lui Floyd utilizează o matrice A de dimensiuni nXn cu ajutorul căreia determină lungimile drumurilor minime. 
• Iniţial se face A[i,j]=COST[i,j] pentru toţi i ≠ j. 
• Dacă nu există niciun arc de la nodul i la nodul j, se presupune că COST[i,j]= ∞. 
• Elementele diagonalei matricei A se pun toate pe 0. 
• Algoritmul lui Floyd execută n iteraţii asupra matricii A. 
• După cea de-a k-a iteraţie, A[i,j] va conţine lungimea minimă a unui drum de la nodul i la nodul j, care nu trece prin nici un nod cu număr mai mare ca şi k.  
• Cu alte cuvinte, i şi j pot fi oricare două noduri ale grafului care delimitează începutul şi sfârşitul drumului, dar orice nod intermediar care intră în alcătuirea drumului trebuie să aibă numărul mai mic sau cel mult egal cu k. 
• Se face precizarea că indicele k semnifică momentul de timp la care se realizează calculul matricei A (în cadrul celei de-a k iteraţii) şi nu faptul că ar exista n matrici A, fiind utilizat pentru o înţelegere mai facilă a funcţionării algoritmului. 
• Pentru calculul lui Ak[i,j] se compară Ak-1[i,j] - adică costul drumului de la i la j fără a trece prin nodul k sau oricare alt nod cu număr mai mare ca şi k, cu Ak-1[i,k]+Ak-1[k,j] - adică costul drumului de la i la k însumat cu costul drumului de la k la j fără a trece prin nici un nod cu număr mai mare ca şi k. 
• Dacă drumul din urmă se dovedeşte a fi mai scurt, atunci el este atribuit valorii Ak[i,j], altfel aceasta rămâne identică cu valoarea anterioară. 
• Pentru graful ponderat din figura 12.2.1.b. (a), se prezintă în cadrul aceleiaşi figuri modul în care se modifică matricea A pornind de la conţinutul ei iniţial A0 şi terminând cu conţinutul său final A3. 

Calculul lungimii drumurilor minime corespunzătoare tuturor perechilor de noduri ale unui graf utilizând algoritmul lui Floyd 

• Deoarece Ak[i,k]=Ak-1[i,k] şi Ak[k,j]=Ak-1[k,j], nici o intrare a matricii A în care intervine pe post de indice valoarea k, nu se modifică în timpul celei de-a k-a iteraţii. 
• Cu alte cuvinte, matricea A este invariantă în raport cu indicele k. 
• În consecinţă se poate utiliza o singură copie a matricii A. 
• Structura de principiu a procedurii care implementează algoritmul lui Floyd în baza considerentelor mai sus enunţate apare în secvenţa [12.2.1.a]. 

------------------------------------------------------------ 

PROCEDURE Floyd(VAR A: ARRAY[1..n,1..n] OF real; 

 COST: ARRAY[1..n,1..n] OF real); 

 

{Procedura determină matricea drumurilor minime A pornind de 

la matricea ponderilor COST} 

 

 VAR i,j k: INTEGER; 

 

 BEGIN 

[1]    FOR i:= 1 TO n DO 

[2]    FOR j:= 1 TO n DO 

[3]    A[i,j]:= COST[i,j];                 [12.2.1.a] 

[4]    FOR i:= 1 TO n DO 

[5]    A[i,i]:= 0; 

[6]    FOR k:= 1 TO n DO 

[7]    FOR i:= 1 TO n DO 

[8]    FOR j:= 1 TO n DO 

[9]      IF A[i,k] + A[k,j] < A[i,j] THEN 

[10]    A[i,j]:= A[i,k] + A[k,j] 

         END; {Floyd} 

------------------------------------------------------------

• Timpul de execuţie al acestei proceduri este în mod clar proporţional cu O(n3) deoarece la baza sa stă o buclă triplă încuibată. 
• Verificarea corectitudinii funcţionării algoritmului se poate realiza simplu prin metoda inducţiei. 
• Astfel este uşor de demonstrat că după ce k trece prin bucla triplă FOR, A[i,j] memorează lungimea celui mai scurt drum de la nodul i la nodul j care în niciun caz nu trece printr-un nod cu număr mai mare ca şi k [AH85].