Algoritmul Roy–Floyd

Algoritmul Roy–Floyd calculează costurile minime între toate perechile de vârfuri. Pornește de la costurile arcelor directe și verifică dacă trecerea printr-un vârf intermediar îmbunătățește un drum. Pentru 1→2 cu cost 4, 2→3 cu cost 3 și 1→3 cu cost 10, trecerea prin 2 reduce costul 1→3 la 7.

Algoritmul Roy–Floyd calculează costurile minime între toate perechile de vârfuri ale unui graf orientat sau neorientat ponderat, fără cicluri de cost negativ. Matricea d conține inițial costul arcului direct (0 pe diagonală, o valoare convențională INF dacă arcul lipsește). Pentru fiecare vârf intermediar k, de la 1 la $n$, se verifică pentru toate perechile $(i,j)$ dacă drumul prin k este mai scurt decât cel cunoscut. Cele trei cicluri imbricate dau timpul $O(n^3)$ și memoria $O(n^2)$. Ordinea ciclurilor contează: ciclul după k trebuie să fie cel exterior. Testul d[i][k]!=INF && d[k][j]!=INF împiedică adunarea unor valori infinite.

Exemplul 1 — trei vârfuri. Arcele sunt $1\to 2$ cu 4, $2\to 3$ cu 3 și $1\to 3$ cu 10:

#include <iostream>
using namespace std;
int main() {
    const int INF = 1000000, n = 3;
    int d[4][4];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) d[i][j] = (i == j ? 0 : INF);
    d[1][2] = 4; d[2][3] = 3; d[1][3] = 10;
    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] > d[i][k] + d[k][j])
                    d[i][j] = d[i][k] + d[k][j];
    cout << d[1][3];
}

Se afișează 7. După folosirea vârfului 2 ca intermediar, d[1][3] devine $4+3=7$, mai mic decât arcul direct de cost 10. Valorile d[2][1], d[3][1] și d[3][2] rămân INF, deoarece nu există drum în sens invers.

Exemplul 2 — reconstituirea drumului. Se păstrează un tablou interm[i][j]: când costul de la i la j se îmbunătățește prin k, se memorează k. Procedura drum(i,j) desparte recursiv drumul în i→k și k→j; dacă nu există intermediar, afișează capătul j, adică arcul direct. Graful are arcele $1\to 2$ cu 3, $2\to 3$ cu 1, $3\to 4$ cu 2 și $1\to 4$ cu 10:

#include <iostream>
using namespace std;
const int INF = 1000000, n = 4;
int d[5][5], interm[5][5];
void drum(int i, int j) {
    int k = interm[i][j];
    if (k == 0) { cout << j << " "; return; }
    drum(i, k);
    drum(k, j);
}
int main() {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) d[i][j] = (i == j ? 0 : INF);
    d[1][2] = 3; d[2][3] = 1; d[3][4] = 2; d[1][4] = 10;
    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] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    interm[i][j] = k;
                }
    cout << d[1][4] << ": 1 ";
    drum(1, 4);
}

Se afișează 6: 1 2 3 4. Pentru k=2 se obține d[1][3]=4 cu interm[1][3]=2, iar d[2][4] rămâne infinit. Pentru k=3 se obțin d[1][4]=4+2=6 cu interm[1][4]=3, în locul arcului direct de cost 10, și d[2][4]=3. Procedura drum(1,4) apelează drum(1,3), care apelează drum(1,2) și drum(2,3), apoi drum(3,4). Drumul minim este $1\to 2\to 3\to 4$.

Exemplul 3 — în formatul examenului. Graful orientat are arcele $1\to 2$ cu 2, $2\to 3$ cu 2, $3\to 1$ cu 1 și $1\to 3$ cu 7. După rularea algoritmului Roy–Floyd, care este valoarea d[2][1]?

• a) 1
• b) 3
• c) 4
• d) infinit

Răspunsul corect este b). Nu există arcul $2\to 1$, dar există drumul $2\to 3\to 1$ cu costul $2+1=3$. Varianta a) este costul arcului $3\to 1$. Varianta c) este d[1][3], adică $2+2=4$ prin vârful 2. Varianta d) ar fi corectă numai dacă nu ar exista niciun drum de la 2 la 1.

Urmărirea matricei din exemplul 2. Notăm INF cu ∞. Inițial liniile sunt 0 3 ∞ 10, ∞ 0 1 ∞, ∞ ∞ 0 2 și ∞ ∞ ∞ 0. Pentru k=1 nu se schimbă nimic, pentru că în vârful 1 nu intră niciun arc. Pentru k=2 se schimbă o singură valoare: d[1][3] devine $3+1=4$. Pentru k=3 se schimbă două: d[1][4] devine $4+2=6$, iar d[2][4] devine $1+2=3$. Pentru k=4 nu se mai îmbunătățește nimic, pentru că din vârful 4 nu pleacă niciun arc. Matricea finală are liniile 0 3 4 6, ∞ 0 1 3, ∞ ∞ 0 2 și ∞ ∞ ∞ 0.

Cazul-limită — ciclul de cost negativ. Dacă există arcele $1\to 2$ cu cost 1 și $2\to 1$ cu cost $-3$, drumul $1\to 2\to 1$ costă $-2$. Pentru k=1, valoarea d[2][2] devine $d[2][1]+d[1][2]=-3+1=-2$, adică o valoare negativă pe diagonală, deși un vârf ajunge în el însuși cu cost 0. Acest semn arată că graful are un ciclu de cost negativ, iar costurile minime nu mai sunt definite, pentru că fiecare parcurgere a ciclului scade din nou costul. De aceea algoritmul se aplică doar grafurilor fără astfel de cicluri.

Greșeli frecvente

• Greșit: metoda calculează doar drumuri dintr-o singură sursă.
  Corect: tratează toate perechile.
• Greșit: un drum inexistent are cost numeric zero.
  Corect: este reprezentat separat, de obicei printr-o valoare infinită convențională.
• Greșit: valoarea directă 10 rămâne minimă.
  Corect: drumul prin 2 costă 7.

Înainte și după