Algoritmul lui Floyd Warshall

Încercați să alegeți cea mai scurtă cale de la locația dvs. la destinație?. Atunci, ar trebui să știți despre acest algoritm.

• Algoritmul lui Floyd-Warshall este folosit pentru a găsi cele mai scurte căi între toate perechile de vârfuri dintr-un graf, unde fiecare muchie din graf are o greutate care este pozitivă sau negativă.
• Cel mai mare avantaj al utilizării acestui algoritm este că toate distanțele cele mai scurte între oricare 2 vârfuri pot fi calculate în O(V3), unde V este numărul de vârfuri dintr-un graf.
• Argitmul Floyd-Warshall mai este numit și algoritmul lui Floyd, algoritmul Roy-Floyd, algoritmul Roy-Warshall sau algoritmul WFI.
• Acest algoritm urmează abordarea programării dinamice pentru a găsi cele mai scurte căi.

Algoritm

Pentru un graf cu N vârfuri:

Etapa 1: Inițializați cele mai scurte căi între oricare 2 vârfuri cu Infinit.

Etapa 2: Găsiți toate perechile celor mai scurte căi care folosesc 0 vârfuri intermediare, apoi găsiți cele mai scurte căi care folosesc 1 vârf intermediar și așa mai departe… până când folosiți toate cele N vârfuri ca noduri intermediare.

Etapa 3: Minimizați cele mai scurte căi între oricare 2 perechi din operația anterioară.

Etapa 4: Pentru oricare 2 vârfuri (i,j) , ar trebui de fapt minimizate distanțele dintre această pereche folosind primele K noduri, astfel încât cea mai scurtă cale va fi: min(dist+dist,dist).

dist reprezintă cea mai scurtă cale care folosește doar primele K vârfuri, dist reprezintă cea mai scurtă cale între perechile k,j. Deoarece cea mai scurtă cale va fi o concatenare a celei mai scurte căi de la i la k, apoi de la k la j.

for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist = min( dist, dist + dist );
}
}
}

Exemplu

Să fie graful dat:

Să se urmeze pașii de mai jos pentru a găsi cea mai scurtă cale între toate perechile de vârfuri.

1. Creați o matrice A0 de dimensiune n*n unde n este numărul de vârfuri. Rândul și coloana sunt indexate ca i și, respectiv, j. i și j sunt vârfurile grafului.

Care celulă A se completează cu distanța de la vîrful ith la vîrful jth. Dacă nu există nici un drum de la vertexul ith la vertexul jth, celula este lăsată la infinit.

2. Acum, creați o matrice A1 folosind matricea A0. Elementele din prima coloană și primul rând sunt lăsate așa cum sunt. Celulele rămase se completează în felul următor:

Să fie k vertexul de îngheț din calea cea mai scurtă de la sursă la destinație. În acest pas, k este primul vertex.A se umple cu (A + A) if (A > A + A).

Chiar dacă distanța directă de la sursă la destinație este mai mare decât drumul prin vertexul k, atunci celula se umple cu A + A.

În acest pas, k este vertexul 1. Se calculează distanța de la vertexul sursă la vertexul destinație prin acest vertex k.

De exemplu: Pentru A1, distanța directă de la vertexul 2 la 4 este 4, iar suma distanțelor de la vertexul 2 la 4 prin vertex (adică de la vertexul 2 la 1 și de la vertexul 1 la 4) este 7. Deoarece 4 < 7, A0 se umple cu 4.

3. În mod similar, A2 se creează A2 folosind A3. Elementele din a doua coloană și al doilea rând sunt lăsate așa cum sunt.

În această etapă, k este al doilea vertex (adică vertexul 2). Restul pașilor sunt aceiași ca în pasul 2.

4. În mod similar, se creează și A3 și A4.

A4 dă cea mai scurtă cale între fiecare pereche de vârfuri.

Încercați să selectați cea mai scurtă cale, apoi folosiți codul de mai jos pentru a o găsi. Dar introduceți distanțele corecte.

Complexitate temporală

Există trei bucle. Fiecare buclă are complexități constante. Deci, complexitatea în timp a algoritmului Floyd-Warshall este O(n3).

Complexitatea spațială

Complexitatea spațială a algoritmului Floyd-Warshall este O(n2).

.