Metode de Reprezentare a Grafurilor: Algoritmul Roy-Floyd 32
1. Ce este Algoritmul Roy-Floyd?
Algoritmul Roy-Floyd (cunoscut și ca Floyd-Warshall) este un algoritm utilizat pentru a determina drumurile minime între toate perechile de noduri dintr-un graf ponderat. Acesta este aplicabil atât pentru grafuri orientate, cât și pentru grafuri neorientate.
2. Obiectiv
- Calcularea matricei distanțelor DDD, unde D[i][j]D[i][j]D[i][j] reprezintă costul minim al unui drum de la nodul iii la nodul jjj.
3. Ideea Algoritmului
Algoritmul Roy-Floyd se bazează pe conceptul de nod intermediar:
- Presupunem că dorim să determinăm distanța minimă D[i][j]D[i][j]D[i][j] între nodurile iii și jjj.
- Considerăm că drumul de la iii la jjj poate trece printr-un nod intermediar kkk.
- Dacă există un drum mai scurt trecând prin kkk, actualizăm distanța: D[i][j]=min(D[i][j],D[i][k]+D[k][j])D[i][j] = \min(D[i][j], D[i][k] + D[k][j])D[i][j]=min(D[i][j],D[i][k]+D[k][j])
4. Pașii Algoritmului
- Inițializare:
- Se pornește de la matricea costurilor CCC a grafului: D[i][j]={C[i][j],daca˘ exista˘ o muchie ıˆntre i și j∞,altfelD[i][j] = \begin{cases} C[i][j], & \text{dacă există o muchie între \( i \) și \( j \)} \\ \infty, & \text{altfel} \end{cases}D[i][j]={C[i][j],∞,daca˘ exista˘ o muchie ıˆntre i și jaltfel
- D[i][i]=0D[i][i] = 0D[i][i]=0 pentru toate iii.
- Actualizare iterativă:
- Pentru fiecare nod intermediar kkk, verificăm toate perechile de noduri (i,j)(i, j)(i,j): D[i][j]=min(D[i][j],D[i][k]+D[k][j])D[i][j] = \min(D[i][j], D[i][k] + D[k][j])D[i][j]=min(D[i][j],D[i][k]+D[k][j])
- Rezultatul final:
- Matricea DDD reprezintă distanțele minime între toate perechile de noduri.
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 distanțelor.
6. Exemplu
Graf Ponderat
Graful:
1 –(5)–> 2
| |
(3) (2)
| |
v v
4 <–(4)– 3
- Matricea Costurilor CCC:
1 2 3 4
1 0 5 ∞ 3
2 ∞ 0 2 ∞
3 ∞ ∞ 0 4
4 ∞ ∞ ∞ 0
- Calculul Matricei Distanțelor DDD: Iterăm prin toți nodurile intermediare kkk și actualizăm D[i][j]D[i][j]D[i][j] conform relației D[i][j]=min(D[i][j],D[i][k]+D[k][j])D[i][j] = \min(D[i][j], D[i][k] + D[k][j])D[i][j]=min(D[i][j],D[i][k]+D[k][j]).
Rezultatul final:
1 2 3 4
1 0 5 7 3
2 ∞ 0 2 6
3 ∞ ∞ 0 4
4 ∞ ∞ ∞ 0
7. Implementare în C++
1. Implementare Generală
#include <iostream>
#include <vector>
#define INF 100000 // Valoare convențională pentru infinit
using namespace std;
void royFloyd(int n, int dist[100][100]) {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != INF && dist[k][j] != INF) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
}
void afisareMatrice(int n, int matrice[100][100]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrice[i][j] == INF)
cout << „INF „;
else
cout << matrice[i][j] << ” „;
}
cout << endl;
}
}
int main() {
int n = 4; // Numărul de noduri
int dist[100][100] = {
{0, 5, INF, 3},
{INF, 0, 2, INF},
{INF, INF, 0, 4},
{INF, INF, INF, 0}
};
cout << „Matricea costurilor inițială:\n”;
afisareMatrice(n, dist);
royFloyd(n, dist);
cout << „\nMatricea distanțelor minime obținută cu Roy-Floyd:\n”;
afisareMatrice(n, dist);
return 0;
}
2. Extensie pentru Detectarea Ciclurilor Negativ
Ciclurile negative apar atunci când suma costurilor de pe un ciclu este negativă.
void detectareCicluriNegative(int n, int dist[100][100]) {
for (int i = 0; i < n; i++) {
if (dist[i][i] < 0) {
cout << „Ciclu negativ detectat care include nodul ” << i + 1 << „!\n”;
}
}
}
8. Aplicații ale Algoritmului Roy-Floyd
- Probleme de navigație:
Determinarea drumurilor minime între toate locațiile într-o hartă. - Analiza rețelelor:
Calcularea costurilor minime între computere într-o rețea. - Optimizarea transportului:
Determinarea costurilor minime pentru livrarea mărfurilor între depozite. - Detectarea ciclurilor negative:
Util pentru detectarea inconsistențelor în rețele ponderate.
9. Concluzie
Algoritmul Roy-Floyd este o soluție elegantă și eficientă pentru calcularea drumurilor minime între toate perechile de noduri dintr-un graf ponderat. Este esențial în optimizarea rețelelor și rezolvarea problemelor de accesibilitate în grafuri complexe.