Drumuri de cost minim într-un graf orientat

Fie G=(V,U) un graf orientat ponderat - în care fiecare arc are asociată o valoare reală numită pondere sau cost, de regulă pozitivă, cu noduri numerotate de la 1 la n.

Se dorește determinarea pentru fiecare pereche de noduri x y, dacă există, a unui drum de cost minim - în care suma costurilor asociate arcelor care definesc drumul este minimă.

Algoritmul pornește matricea costurilor , A - în care:

În reprezentarea în memorie, ∞ va fi înlocuit cu o valoare numerică mare. În C++, aceasta poate fi INF = 0x3F3F3F3F, având următoarele avantaje:

INF se reprezintă în tipul int (pe 32 de biți cu semn) și este mai mare decât 1.000.000.000
suma INF + INF nu depășește limita maximă a tipului int, deci nu va face overflow.

Prin algoritmul Roy-Floyd matricea va fi transformată, astfel încât la final va avea următoarea semnificație:

Justificare algorimului

Pentru graful G=(V,U) , cu noduri numerotate de la 1 la n , considerăm funcția costMin(i,j,k), reprezentând pentru fiecare pereche de noduri i,j costul minim al unui drum de la i la j având noduri intermediare numai din mulțimea 1,2,...,k. Atunci, problema revine la a determina pentru fiecare pereche de noduri i,j valoarea costMin(i,j,n).

Pentru fiecare pereche i,j , costMin(i,j,0)=costul arcului (i,j), - drumul de la i la j nu conține noduri intermediare, iar pentru un k oarecare, costMin(i,j,k) poate fi una dintre următoarele valori:

drumul de la i la j nu trece prin nodul k: costMin(i,j,k−1)
drumul de la i la j trece prin nodul k - de la i la k și de la k la j, cu noduri intermediare din mulțimea 1,2,...,k−1: costMin(i,k,k−1)+costMin(k,j,k−1).

Atunci, pentru fiecare costMin(i,j,k) se va alege minimul dintre cele două valori de mai sus: costMin(i,j,k)=min(costMin(i,j,k−1) ,costMin(i,k,k−1)+costMin(k,j,k−1)).

Această formulă este cheia algoritmului Roy-Floyd. Algoritmul determină mai întâi costMin(i,j,1), pentru toate perechile i,j, apoi costMin(i,j,2), apoi costMin(i,j,3), etc.

Secvență C++

//D[][] este inițial matricea costurilor arcelor

for(int k = 1 ; k <= n ; k ++)

for(int i = 1 ; i <= n ; i ++)

for(int j = 1 ; j <= n ; j ++)

if(D[i][j] > D[i][k] + D[k][j])

D[i][j] = D[i][k] + D[k][j];

Probleme ataşate

#0589 - Roy-Floyd

Vezi și: