Hanusz MnikaGr.213Laborator 2Algoritmul lui Floyd Warshall Hu

1.Formulare enunS se determine un drum de valoare minim de la un vrf p la un vrf q cu ajutorul algoritmului matricial Floyd Warshall Hu2.O propunere de dezvoltare de algoritmAlgoritmul Floyd-Warshall compar toate drumurile posibile din graf dintre fiecare 2 noduri, i poate fi utilizat i in grafuri cu muchii de valoare negativ.Calculeaz drumurile minime ntre oricare dou noduri din graf, poate fi folosit n grafuri cu cicluri de valoare negativ, dar nu le detecteaz.

3.Descrierea algoritmuluifor i := 0 to n-1 do for j := 0 to n-1 do if i == j then D[i,j] := 0; else if (i,j) is in E then D[i,j] := w(i,j); else D[i,j] := oo; end ifend if end for end for for k := 0 to n-1 do for i := 0 to n-1 do for j := 0 to n-1 do if D[i,k] + D[k,j] < D[i,j] then D[i,j] = D[i,k] + D[k,j]; end if end for end for end for END

4.Demonstrarea corectitudinii algoritmuluiEstimarea drumului optim poate fi reinut ntr-o structur tridimensional d[p, q, k], cu semnificaia valoarea minim al drumului de la p la q, folosind ca noduri intermediare doar noduri pana la nodul k. Daca nodurile sunt numerotate de la 1, atunci d[p, q, 0] reprezint valoarea muchiei directe de la p la q, considernd + daca aceasta nu exista. Exemplu, pentru p = 1, respectiv 2:

Pornind cu valori ale lui k de la 1 la |V|, ne intereseaz s gsim cea mai scurt cale de la fiecare p la fiecare q folosind doar noduri intermedire din mulimea {1, , k}. De fiecare dat, comparm valoarea deja estimat al drumului de la p la q, deci d[p, q, k-1] obinut la pasul anterior, cu valoarea drumurilor de la p la k si de la k la q, adic d[p, k, k-1] + d[k, q, k-1], obinut la pasul anterior. Atunci, d[p, q, |V|] va conine valoarea drumului minim de la p la q.Pentru a determina drumul efectiv, nu doar valoarea acestuia, avem dou variante:Se folosete divide et impera astfel:- se caut un pivot k astfel nct val[i][j] = val[i][k] + val[j][k]- se apeleaz funcia recursiv pentru ambele drumuri (i,k),(k,j)- dac pivotul nu poate fi gsit, afim i- dup terminarea funciei recursie afim extremitatea dreapta a drumului5.Cod surs

#include using namespace std;

int main(){

// Initializare int vertices = 5; vector > a(vertices, vector(vertices,999999999));

// initializare diagonala for(int i=0; i < vertices; i++) a[i][i]=0

// initialize distanta a[0][1]=20; a[0][2]=10; a[0][4]=5; a[2][3]=10; a[3][1]=3; a[4][2]=2; a[4][3]=4;

// Floyd-Warshall // Add nodes between (first 1 then 2, 3 till n) and look if // distance is shorter for(int k = 0; k < vertices; k++) for(int i = 0; i < vertices; i++) for(int j = 0; j < vertices; j++) if(a[i][j]>a[i][k]+a[k][j]) a[i][j]=a[i][k]+a[k][j];

// Print out final distance matrix for(int i = 0; i < vertices; i++){ for(int j = 0; j < vertices; j++) cout