Matricea drumurilor

Fie \( G=(V,U) \) un graf orientat cu \( n \) noduri. Algoritmul Roy-Warshall construiește matricea drumurilor: \( D \) cu \( n \) linii și \( n \) coloane, în care:

$$ D_{i,j} = \begin{cases}
0& \text{dacă } i = j \text{ sau nu există drum de la } i \text{ la } j,\\
1& \text{dacă } i \neq j \text{ și există drum de la } i \text{ la } j
\end{cases} $$

Conform definiției de mai sus, în matricea drumurilor, elementele cu indici egali vor avea întotdeauna valoarea \( 0 \). Alternativ, putem accepta și elemente \( D_{i,i} = 1 \), înțelegând prin asta că există un circuit care conține nodul \( i \).

Pentru a construi această matrice, se pornește de la matricea de adiacență și i se aplică o serie de transformări, pornind de la următoarea idee: dacă nu există drum de la \( i \) la \( j \), dar există drum de la \( i \) la \( k \) și drum de la \( k \) la \( j \), atunci va exista și drum de la \( i \) la \( j \), prin reuniunea celor două drumuri existente.

Mai exact:

• inițial avem numai drumurile care nu au noduri intermediare (arcele)
• determinăm toate drumurile care îl au eventual ca nod intermediar pe \( 1\)
• determinăm toate drumurile care au noduri intermediare numai din mulțimea \( \left\{1,2\right\} \)
• determinăm toate drumurile care au noduri intermediare numai din mulțimea \( \left\{1,2,3\right\} \)
  …
• pentru un \( k \) oarecare, determinăm toate drumurile care au noduri intermediare numai din mulțimea \( \left\{1,2,…,k\right\} \). Pentru aceasta, vom căuta toate perechile de noduri \( i,j \) astfel încât \( D_{i,k} = 1 \) și \( D_{k,j} = 1 \), de unde va rezulta că și \( D_{i,j} = 1 \).

Secvența C++

Secvență C++ – elementele de pe diagonală rămân 0:

// a - matricea de adiacență
for(int k = 1 ; k <= n ; ++k)
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            if( i != j && a[i][j] == 0 &&  a[i][k] == 1 && a[k][j] == 1)
                a[i][j] = 1;

O variantă mai condensată este următoarea:

// D este matricea de adiacență
for(int k = 1 ; k <= n ; ++k)
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            if( i != j && a[i][j] == 0)
                a[i][j] = a[i][k] * a[k][j];

Următoarea versiune transformă în 1 și elementele de pe diagonală care corespund unor noduri care fac parte din cel puțin un circuit.

// D este matricea de adiacență
for(int k = 1 ; k <= n ; ++k)
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            if(a[i][j] == 0)
                a[i][j] = a[i][k] * a[k][j];

Reconstituirea drumurilor

Pentru reconstituirea drumurilor vom folosi atât matricea drumurilor cât și matricea de adiacență. Fie acestea \( D\), respectiv \( A \), iar reconstituirea se bazează pe următorul algoritm recursiv, de tip Divide-et-Impera:

• reconstituim drumul de la \( i \) la \( j \) – știm că \( D_{i,j} = 1 \):
  • dacă există arc de la \( i \) la \( j \) (adică \( A_{i,j} = 1\) ), atunci acest arc reprezintă și drumul căutat
  • dacă nu există arc, căutăm un nod k pentru care \( D_{i,k} = 1 \) și \( D_{k,j} = 1 \) și reconstituim prin apeluri recursive drumurile de la \( i \) la \( k \) și de la \( k \) la \( j \).