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:

$$ A_{i,j} = \begin{cases}
0& \text{dacă } i = j,\\
\text{costul arcului } (i,j)& \text{ dacă există arc de la } i \text{ la } j,\\
\infty & \text{ dacă nu există arc de la } i \text{ la } j
\end{cases} $$

În reprezentarea în memorie, \( \infty \) 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:

$$ D_{i,j} = \begin{cases}
0& \text{dacă } i = j,\\
\text{costul minim al unui drum de la } i \text{ la } j& \text{ dacă există un asemenea drum },\\
\infty & \text{ dacă nu există drum de la } i \text{ la } j
\end{cases} $$

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) = \text{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];