Metode de Reprezentare a Grafurilor: Algoritmul Roy-Warshall 31

---

1. Ce este Algoritmul Roy-Warshall?

Algoritmul Roy-Warshall este un algoritm utilizat pentru a determina matricea drumurilor într-un graf. Mai exact, acest algoritm determină dacă există un drum între două noduri iii și jjj într-un graf (orientat sau neorientat).

---

2. Obiectiv

• Construirea matricei drumurilor PPP, unde: P[i][j]={1,daca˘ exista˘ un drum de la i la j0,altfelP[i][j] = \begin{cases} 1, & \text{dacă există un drum de la \( i \) la \( j \)} \\ 0, & \text{altfel} \end{cases}P[i][j]={1,0,​daca˘ exista˘ un drum de la i la jaltfel​

---

3. Ideea Algoritmului

Algoritmul Roy-Warshall se bazează pe conceptul de nod intermediar:

• Presupunem că putem ajunge de la nodul iii la nodul jjj trecând printr-un alt nod kkk.
• Dacă există un drum de la iii la kkk și un drum de la kkk la jjj, atunci există un drum de la iii la jjj.

---

4. Pas cu Pas

1. Inițializare:
   • Se folosește matricea de adiacență AAA a grafului ca punct de plecare: P[i][j]=A[i][j],∀i,jP[i][j] = A[i][j], \forall i, jP[i][j]=A[i][j],∀i,j
2. Actualizare iterativă:
   • Pentru fiecare nod kkk (considerat ca nod intermediar), se verifică dacă: P[i][j]=P[i][j]∨(P[i][k]∧P[k][j])P[i][j] = P[i][j] \lor (P[i][k] \land P[k][j])P[i][j]=P[i][j]∨(P[i][k]∧P[k][j])
   • Asta înseamnă că, dacă există un drum de la iii la jjj trecând prin kkk, se actualizează valoarea P[i][j]P[i][j]P[i][j] la 1.
3. Rezultatul final:
   • Matricea PPP reprezintă matricea drumurilor pentru graf.

---

5. Complexitate

• Timp: O(∣V∣3)O(|V|^3)O(∣V∣3), unde ∣V∣|V|∣V∣ este numărul de noduri.
• Spațiu: O(∣V∣2)O(|V|^2)O(∣V∣2), pentru stocarea matricei PPP.

---

6. Exemplu

Graf Orientat

(1) → (2)

 ↑      ↓

(4) ← (3)

• Matricea de adiacență AAA:

    1  2  3  4

1   0  1  0  0

2   0  0  1  0

3   0  0  0  1

4   1  0  0  0

• Calcularea PPP:
  • Inițial, P=AP = AP=A.
  • După actualizarea cu k=1k = 1k=1, k=2k = 2k=2, k=3k = 3k=3, k=4k = 4k=4:

    1  2  3  4

1   1  1  1  1

2   1  1  1  1

3   1  1  1  1

4   1  1  1  1

---

7. Implementare în C++

#include <iostream>

using namespace std;

void royWarshall(int n, int matrice[100][100]) {

    for (int k = 0; k < n; k++) {

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                matrice[i][j] = matrice[i][j] || (matrice[i][k] && matrice[k][j]);

            }

        }

    }

}

void afisareMatrice(int n, int matrice[100][100]) {

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            cout << matrice[i][j] << ” „;

        }

        cout << endl;

    }

}

int main() {

    int n = 4;

    int matrice[100][100] = {

        {0, 1, 0, 0},

        {0, 0, 1, 0},

        {0, 0, 0, 1},

        {1, 0, 0, 0}

    };

    cout << „Matricea de adiacență inițială:\n”;

    afisareMatrice(n, matrice);

    royWarshall(n, matrice);

    cout << „\nMatricea drumurilor obținută cu Roy-Warshall:\n”;

    afisareMatrice(n, matrice);

    return 0;

}

---

8. Aplicații ale Algoritmului Roy-Warshall

1. Analiza conectivității:
   • Determinarea dacă un graf este conex (neorientat) sau tare conex (orientat).
2. Accesibilitate:
   • Verificarea dacă există un drum între două noduri.
3. Optimizare în rețele:
   • Analiza conexiunilor posibile într-o rețea de transport sau calculatoare.
4. Determinarea ciclurilor:
   • Dacă P[i][i]=1P[i][i] = 1P[i][i]=1 pentru un nod iii, atunci există un ciclu.

---

9. Concluzie

Algoritmul Roy-Warshall este o soluție elegantă și eficientă pentru calcularea matricei drumurilor într-un graf. Este aplicabil atât pentru grafuri orientate, cât și neorientate, și oferă informații fundamentale despre conectivitatea nodurilor.