Algoritmul Floyd-Warshall

În acest tutorial, veți afla cum funcționează algoritmul Floyd-Warshall. De asemenea, veți găsi exemple de lucru ale algoritmului floyd-warshall în C, C ++, Java și Python.

Algoritmul Floyd-Warshall este un algoritm pentru găsirea celei mai scurte căi între toate perechile de vârfuri într-un grafic ponderat. Acest algoritm funcționează atât pentru graficele ponderate direcționate, cât și pentru cele nedirecționate. Dar nu funcționează pentru graficele cu cicluri negative (unde suma marginilor dintr-un ciclu este negativă).

Un grafic ponderat este un grafic în care fiecare margine are o valoare numerică asociată.

Algoritmul Floyd-Warhshall este, de asemenea, numit algoritmul lui Floyd, algoritmul Roy-Floyd, algoritmul Roy-Warshall sau algoritmul WFI.

Acest algoritm urmează abordarea de programare dinamică pentru a găsi cele mai scurte căi.

Cum funcționează algoritmul Floyd-Warshall?

Fie graficul dat să fie:

Grafic inițial

Urmați pașii de mai jos pentru a găsi cea mai scurtă cale între toate perechile de vârfuri.

  1. Creați o matrice de dimensiune în care n este numărul de vârfuri. Rândul și coloana sunt indexate ca i și respectiv j. i și j sunt vârfurile graficului. Fiecare celulă A (i) (j) este umplută cu distanța de la vârf la vârf. Dacă nu există o cale de la vârf la vârf, celula este lăsată ca infinit. Umpleți fiecare celulă cu distanța dintre vârful ith și jthA0n*n
    ithjthithjth
  2. Acum, creați o matrice folosind matricea . Elementele din prima coloană și primul rând sunt lăsate așa cum sunt. Celulele rămase sunt umplute în felul următor. Fie k vârful intermediar în cea mai scurtă cale de la sursă la destinație. În acest pas, k este primul vârf. este umplut cu . Adică, dacă distanța directă de la sursă la destinație este mai mare decât calea prin vârful k, atunci celula este umplută cu . În acest pas, k este vârful 1. Calculăm distanța de la vârful sursă la vârful destinației prin acest vârf k. Calculați distanța de la vârful sursă la vârful destinației prin acest vârf k De exemplu: PentruA1A0
    A(i)(j)(A(i)(k) + A(k)(j)) if (A(i)(j)> A(i)(k) + A(k)(j))
    A(i)(k) + A(k)(j)

    A1(2, 4), distanța directă de la vârful 2 la 4 este 4 și suma distanței de la vârful 2 la 4 prin vârf (adică de la vârful 2 la 1 și de la vârful 1 la 4) este 7. Deoarece 4 < 7, este umplut cu 4.A0(2, 4)
  3. În mod similar, este creat folosind . Elementele din a doua coloană și al doilea rând sunt lăsate așa cum sunt. În acest pas, k este al doilea vârf (adică vârful 2). Pașii rămași sunt aceiași ca la pasul 2 . Calculați distanța de la vârful sursă la vârful destinației prin acest vârf 2A2A3
  4. În mod similar, și este, de asemenea, creat. Calculați distanța de la vârful sursă la vârful de destinație prin acest vârf 3 Calculați distanța de la vârful sursă la vârful de destinație prin acest vârf 4A3A4
  5. A4 dă cea mai scurtă cale între fiecare pereche de vârfuri.

Algoritmul Floyd-Warshall

n = nr de vârfuri A = matrice de dimensiune n * n pentru k = 1 la n pentru i = 1 la n pentru j = 1 la n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) returnează A

Exemple Python, Java și C / C ++

Python Java C C ++ 
 # Floyd Warshall Algorithm in python # The number of vertices nV = 4 INF = 999 # Algorithm implementation def floyd_warshall(G): distance = list(map(lambda i: list(map(lambda j: j, i)), G)) # Adding vertices individually for k in range(nV): for i in range(nV): for j in range(nV): distance(i)(j) = min(distance(i)(j), distance(i)(k) + distance(k)(j)) print_solution(distance) # Printing the solution def print_solution(distance): for i in range(nV): for j in range(nV): if(distance(i)(j) == INF): print("INF", end=" ") else: print(distance(i)(j), end=" ") print(" ") G = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)) floyd_warshall(G)
 // Floyd Warshall Algorithm in Java class FloydWarshall ( final static int INF = 9999, nV = 4; // Implementing floyd warshall algorithm void floydWarshall(int graph()()) ( int matrix()() = new int(nV)(nV); int i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()()) ( for (int i = 0; i < nV; ++i) ( for (int j = 0; j < nV; ++j) ( if (matrix(i)(j) == INF) System.out.print("INF "); else System.out.print(matrix(i)(j) + " "); ) System.out.println(); ) ) public static void main(String() args) ( int graph()() = ( ( 0, 3, INF, 5 ), ( 2, 0, INF, 4 ), ( INF, 1, 0, INF ), ( INF, INF, 2, 0 ) ); FloydWarshall a = new FloydWarshall(); a.floydWarshall(graph); ) )
 // Floyd-Warshall Algorithm in C #include // defining the number of vertices #define nV 4 #define INF 999 void printMatrix(int matrix()(nV)); // Implementing floyd warshall algorithm void floydWarshall(int graph()(nV)) ( int matrix(nV)(nV), i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()(nV)) ( for (int i = 0; i < nV; i++) ( for (int j = 0; j < nV; j++) ( if (matrix(i)(j) == INF) printf("%4s", "INF"); else printf("%4d", matrix(i)(j)); ) printf(""); ) ) int main() ( int graph(nV)(nV) = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)); floydWarshall(graph); )
 // Floyd-Warshall Algorithm in C++ #include using namespace std; // defining the number of vertices #define nV 4 #define INF 999 void printMatrix(int matrix()(nV)); // Implementing floyd warshall algorithm void floydWarshall(int graph()(nV)) ( int matrix(nV)(nV), i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()(nV)) ( for (int i = 0; i < nV; i++) ( for (int j = 0; j < nV; j++) ( if (matrix(i)(j) == INF) printf("%4s", "INF"); else printf("%4d", matrix(i)(j)); ) printf(""); ) ) int main() ( int graph(nV)(nV) = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)); floydWarshall(graph); )

Floyd Warshall Algorithm Complexity

Complexitatea timpului

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)

Aplicații pentru algoritmul Floyd Warshall

  • Pentru a găsi cea mai scurtă cale este un grafic direcționat
  • Pentru a găsi închiderea tranzitivă a graficelor direcționate
  • Pentru a găsi Inversiunea matricilor reale
  • Pentru a testa dacă un grafic nedirecționat este bipartit

Articole interesante...