Matricea drumurilor

Matricea drumurilor arată dacă se poate ajunge de la un vârf la altul printr-un drum, nu doar printr-un arc direct. Pentru arcele 1→2 și 2→3, există drum 1→3, chiar dacă nu există arcul direct 1→3. Poziția corespunzătoare perechii $(1,3)$ este astfel adevărată în matricea drumurilor.

Matricea drumurilor (închiderea tranzitivă) are drum[i][j]=1 dacă în graful orientat există cel puțin un drum de lungime cel puțin 1 de la $i$ la $j$, și 0 în caz contrar. Spre deosebire de matricea de adiacență, ea cuprinde accesibilitatea prin mai multe arce. Algoritmul Roy–Warshall pornește de la matricea de adiacență. Pentru fiecare vârf intermediar $k$, de la 1 la $n$, se parcurg toate perechile $(i,j)$: dacă există drum de la $i$ la $k$ și de la $k$ la $j$, se marchează un drum de la $i$ la $j$. Ciclul după $k$ trebuie să fie cel exterior. Cele trei cicluri dau timpul $O(n^3)$ și memoria $O(n^2)$; lucrează numai cu 0 și 1, deci nu are nevoie de costuri.

Exemplul 1 — un graf fără circuite. Arcele sunt $1\to 2$ și $2\to 3$:

#include <iostream>
using namespace std;
int main() {
    const int n = 3;
    int drum[4][4] = {{0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {0, 0, 0, 0}};
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (drum[i][k] && drum[k][j]) drum[i][j] = 1;
    cout << drum[1][3];
}

Se afișează 1: la k=2, există drum[1][2] și drum[2][3], deci drum[1][3] devine 1, prin vârful 2. Diagonala nu se completează automat: drum[i][i]=1 numai dacă există un circuit care trece prin i. În acest exemplu, fără circuite, diagonala rămâne zero.

Exemplul 2 — un graf cu circuit. Graful are 4 vârfuri și arcele $1\to 2$, $2\to 3$, $3\to 1$, $3\to 4$. Programul calculează matricea drumurilor, o afișează și numără valorile 1:

#include <iostream>
using namespace std;
int main() {
    const int n = 4;
    int d[5][5] = {};
    d[1][2] = d[2][3] = d[3][1] = d[3][4] = 1;
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (d[i][k] && d[k][j]) d[i][j] = 1;
    int total = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cout << d[i][j] << " ";
            total += d[i][j];
        }
        cout << "\n";
    }
    cout << total;
}

Se afișează liniile 1 1 1 1, 1 1 1 1, 1 1 1 1 și 0 0 0 0, apoi 12. Vârfurile 1, 2 și 3 se află pe circuitul $1\to 2\to 3\to 1$, deci fiecare ajunge la toate cele trei, inclusiv la el însuși (diagonala este 1), și la 4, prin arcul $3\to 4$. Din 4 nu pleacă niciun arc, deci linia 4 este zero. Două vârfuri $i$ și $j$ sunt în aceeași componentă tare conexă dacă drum[i][j] și drum[j][i] sunt 1: aici 1, 2 și 3 formează o componentă, iar 4 este singur.

Exemplul 2 bis — de ce k este ciclul exterior. Fie graful cu arcele $1\to 2$, $2\to 3$ și $3\to 1$. Cu ordinea corectă (k, apoi i, apoi j) toate cele nouă elemente ale matricei devin 1, pentru că fiecare vârf ajunge la toate, inclusiv la el însuși, prin circuit. Dacă ciclul după k se pune în interior (ordinea i, j, k), pentru i = 1 și j = 1 se verifică drum[1][k] && drum[k][1] când drumul $1\to 2\to 3\to 1$ încă nu este înregistrat: drum[2][1] este 0 și drum[1][3] tot. Elementul drum[1][1] rămâne 0, deși există circuit. Ordinea greșită pierde drumuri care trec prin vârfuri intermediare descoperite mai târziu.

Exemplul 3 — în formatul examenului. Pentru graful orientat din al doilea exemplu, câte elemente egale cu 1 are matricea drumurilor?

• a) 4
• b) 9
• c) 12
• d) 16

Răspunsul corect este c). Vârfurile 1, 2 și 3 ajung fiecare la toate cele patru vârfuri, deci $3\cdot 4=12$ elemente egale cu 1; vârful 4 nu ajunge nicăieri. Varianta a) este numărul arcelor, adică elementele matricei de adiacență. Varianta b) numără numai perechile din interiorul circuitului și uită că 3 ajunge la 4 și, prin 3, ajung și 1 și 2. Varianta d) ar însemna că și 4 ajunge la toate vârfurile.

Greșeli frecvente

• Greșit: matricea drumurilor este identică cu matricea de adiacență.
  Corect: include și accesibilitatea prin mai multe arce.
• Greșit: dacă nu există arcul direct 1→3, vârful 1 nu poate ajunge la 3.
  Corect: există drumul 1→2→3, deci în matricea drumurilor poziția $(1,3)$ este 1.
• Greșit: dacă 1 ajunge la 3, și 3 ajunge la 1.
  Corect: sensul arcelor contează.

Înainte și după