Roy–Warshall și Roy–Floyd: drumuri în grafuri

Roy–Warshall determină accesibilitatea între toate perechile de vârfuri, iar Roy–Floyd calculează costurile minime între toate perechile. Ambele folosesc aceeași idee de programare dinamică: introducem pe rând vârfurile care pot apărea în interiorul unui drum.

Numele sunt folosite uneori împreună, dar rezultatele diferă. Matricea de accesibilitate conține valori logice; matricea distanțelor conține costuri și o reprezentare a absenței unui drum.

Cum funcționează

La pasul k, verificăm dacă un drum de la i la j poate fi îmbunătățit trecând prin k. Pentru costuri, tranziția este d[i][j]=min(d[i][j],d[i][k]+d[k][j]). Pentru accesibilitate, folosim r[i][j] = r[i][j] || (r[i][k] && r[k][j]). Bucla lui k trebuie să fie cea exterioară, fiindcă ea exprimă starea dinamică, nu doar un indice interschimbabil.

Inițial, costul de la un vârf la el însuși este zero, prin drumul vid. Pentru arce avem costurile citite, iar restul pozițiilor sunt INF. Dacă există arce paralele, păstrăm minimul. Înainte de adunare verificăm că ambele fragmente de drum există, evitând operațiile aritmetice cu INF.

Programul de mai jos presupune 1 <= n <= 100 și costuri nenegative de cel mult un miliard. Algoritmul poate fi folosit și cu costuri negative dacă nu există circuite negative relevante, dar acea situație cere alte convenții de rezultat și verificări. După calcul, o diagonală negativă indică existența unui circuit negativ accesibil din acel vârf; pentru perechile afectate nu mai există un cost minim finit.

Exemplu urmărit pas cu pas

Pentru 1→2 cu cost 4, 2→3 cu cost 7 și 1→3 cu cost 20, introducerea intermediarului 2 permite reducerea distanței 1→3 la 11. Nu adăugăm un arc fizic în graf, ci memorăm costul unui drum care poate avea mai multe arce.

Dacă nu există drum de la 3 la 1, acea poziție rămâne INF și este afișată ca -1 în exemplu. Costul 1→1 rămâne zero. Pentru matricea booleană trebuie precizat dacă accesibilitatea include drumul vid; inițializarea diagonalei cu adevărat adoptă această convenție.

Implementare C++17

Varianta cu tablou clasic:

#include <algorithm>
#include <iostream>
int main() {
    int n, m;
    std::cin >> n >> m;
    const long long INF = 4000000000000000000LL;
    long long d[101][101];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            d[i][j] = (i == j ? 0 : INF);
    for (int t = 0; t < m; ++t) {
        int x, y;
        long long w;
        std::cin >> x >> y >> w;
        d[x][y] = std::min(d[x][y], w);
    }
    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] != INF && d[k][j] != INF)
                    d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            std::cout << (d[i][j] == INF ? -1 : d[i][j]) << (j == n ? '\n' : ' ');
    }
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <algorithm>
#include <iostream>
#include <vector>
int main() {
    int n, m;
    std::cin >> n >> m;
    const long long INF = 4000000000000000000LL;
    std::vector<std::vector<long long>> d(n + 1, std::vector<long long>(n + 1));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            d[i][j] = (i == j ? 0 : INF);
    for (int t = 0; t < m; ++t) {
        int x, y;
        long long w;
        std::cin >> x >> y >> w;
        d[x][y] = std::min(d[x][y], w);
    }
    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] != INF && d[k][j] != INF)
                    d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            std::cout << (d[i][j] == INF ? -1 : d[i][j]) << (j == n ? '\n' : ' ');
    }
}

De ce funcționează și cât costă

După pasul k, d[i][j] reprezintă minimul pentru drumurile ale căror vârfuri interioare sunt dintre primele k. Un drum optim fie nu folosește k, fie se descompune în i→k și k→j. Tranziția compară exact aceste două situații.

Trei bucle pe n vârfuri dau O(n³) timp și matricea ocupă O(n²) memorie. Pentru multe întrebări între perechi pe un graf mic, precalcularea poate fi potrivită. Pentru un graf rar foarte mare, alte metode sunt necesare.

Greșeli frecvente

Nu reordona arbitrar buclele și nu considera că orice valoare mare este un INF sigur. Distinge între un arc absent și un drum absent după precalculare. Pentru trasee efective trebuie păstrată suplimentar informația de reconstrucție.

Exersează

Adaugă arcul 3→1 cu cost 2 în exemplu. Calculează costul minim 2→1.

Rezolvare explicată: Traseul 2→3→1 costă 7+2=9. Apar și drumuri noi între alte perechi, însă diagonalele rămân zero pentru că toate costurile sunt nenegative.

Continuă să înveți

Drumuri minime, grafuri orientate și programare dinamică.

Întrebări frecvente

Ce diferență există între Roy–Warshall și Roy–Floyd?

Prima variantă răspunde dacă există drumuri, iar a doua calculează costurile lor minime. Tranzițiile folosesc operații diferite asupra unor matrici cu semnificații diferite.

De ce intermediarul k este în bucla exterioară?

Fiecare etapă permite un vârf intermediar nou. Această ordine păstrează invariantul programării dinamice; schimbarea arbitrară a buclelor poate lăsa drumuri neactualizate.

De ce pun zero pe diagonală?

Adoptăm convenția drumului vid, care duce de la un vârf la el însuși fără cost. Această inițializare trebuie distinsă de existența unei bucle în graf.

Ce înseamnă o diagonală negativă?

În varianta care admite costuri negative, ea arată existența unui circuit negativ. Drumurile afectate pot avea costuri fără limită inferioară prin repetarea circuitului.

Când aleg Floyd în loc de Dijkstra?

Floyd este simplu pentru toate perechile pe grafuri mici. Dijkstra calculează de la o sursă și cere costuri nenegative; alegerea depinde și de dimensiuni și densitate.