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:

Conform definiției de mai sus, în matricea drumurilor, elementele cu indici egali vor avea întotdeauna valoarea 0. Alternativ, putem accepta și elemente Di,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 {1,2}
• determinăm toate drumurile care au noduri intermediare numai din mulțimea {1,2,3}
  ...
• pentru un k oarecare, determinăm toate drumurile care au noduri intermediare numai din mulțimea {1,2,...,k}. Pentru aceasta, vom căuta toate perechile de noduri i,j astfel încât Di,k=1 și Dk,j=1 , de unde va rezulta că și Di,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ă Di,j=1:
  • dacă există arc de la i la j (adică Ai,j=1), atunci acest arc reprezintă și drumul căutat
  • dacă nu există arc, căutăm un nod k pentru care Di,k=1 și Dk,j=1 și reconstituim prin apeluri recursive drumurile de la i la k și de la k la j.

Probleme ataşate

#0580 - Roy-Warshall

#0587 - Mall 

Vezi și:

• Matricea drumurilor
• Drumuri de cost minim într-un graf orientat