Algoritmo di Floyd-Warshall

In questo tutorial imparerai come funziona l'algoritmo di floyd-warshall. Inoltre, troverai esempi funzionanti dell'algoritmo floyd-warshall in C, C ++, Java e Python.

Floyd-Warshall Algorithm è un algoritmo per trovare il percorso più breve tra tutte le coppie di vertici in un grafo ponderato. Questo algoritmo funziona sia per i grafici pesati diretti che non orientati. Ma non funziona per i grafici con cicli negativi (dove la somma degli archi in un ciclo è negativa).

Un grafico ponderato è un grafico in cui ogni bordo ha un valore numerico associato ad esso.

L'algoritmo di Floyd-Warhshall è anche chiamato algoritmo di Floyd, algoritmo di Roy-Floyd, algoritmo di Roy-Warshall o algoritmo WFI.

Questo algoritmo segue l'approccio della programmazione dinamica per trovare i percorsi più brevi.

Come funziona l'algoritmo di Floyd-Warshall?

Lascia che il grafico dato sia:

Grafico iniziale

Segui i passaggi seguenti per trovare il percorso più breve tra tutte le coppie di vertici.

  1. Crea una matrice di dimensione dove n è il numero di vertici. La riga e la colonna sono indicizzate rispettivamente come i e j. i e j sono i vertici del grafo. Ogni cella A (i) (j) è riempita con la distanza dal vertice al vertice. Se non è presente alcun percorso da vertice a vertice, la cella viene lasciata all'infinito. Riempi ogni cella con la distanza tra i esimo e il jesimo verticeA0n*n
    ithjthithjth
  2. Ora, crea una matrice usando matrix . Gli elementi nella prima colonna e nella prima riga vengono lasciati come sono. Le celle rimanenti vengono riempite nel modo seguente. Sia k il vertice intermedio nel percorso più breve dalla sorgente alla destinazione. In questo passaggio, k è il primo vertice. è pieno di . Cioè, se la distanza diretta dalla sorgente alla destinazione è maggiore del percorso attraverso il vertice k, la cella viene riempita . In questo passaggio, k è il vertice 1. Calcoliamo la distanza dal vertice di origine al vertice di destinazione attraverso questo vertice k. Calcola la distanza dal vertice di origine al vertice di destinazione attraverso questo vertice k Ad esempio: ForA1A0
    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), la distanza diretta dal vertice 2 a 4 è 4 e la somma della distanza dal vertice 2 a 4 attraverso il vertice (cioè. dal vertice 2 a 1 e dal vertice 1 a 4) è 7. Poiché 4 < 7, è riempito con 4.A0(2, 4)
  3. Allo stesso modo, viene creato utilizzando . Gli elementi nella seconda colonna e nella seconda riga vengono lasciati come sono. In questa fase, k è il secondo vertice (cioè vertice 2). I passaggi rimanenti sono gli stessi del passaggio 2 . Calcola la distanza dal vertice di origine al vertice di destinazione attraverso questo vertice 2A2A3
  4. Allo stesso modo, ed è anche creato. Calcola la distanza dal vertice di origine al vertice di destinazione attraverso questo vertice 3 Calcola la distanza dal vertice di origine al vertice di destinazione attraverso questo vertice 4A3A4
  5. A4 fornisce il percorso più breve tra ogni coppia di vertici.

Algoritmo di Floyd-Warshall

n = no di vertici A = matrice di dimensione n * n per k = 1 an per i = 1 an per j = 1 an A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) restituiscono A

Esempi di Python, Java e 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); )

Complessità dell'algoritmo di Floyd Warshall

Complessità temporale

Ci sono tre loop. Ogni ciclo ha complessità costanti. Quindi, la complessità temporale dell'algoritmo di Floyd-Warshall è .O(n3)

Complessità spaziale

La complessità spaziale dell'algoritmo di Floyd-Warshall è .O(n2)

Applicazioni dell'algoritmo di Floyd Warshall

  • Per trovare il percorso più breve è un grafico diretto
  • Trovare la chiusura transitiva di grafi diretti
  • Per trovare l'inversione di matrici reali
  • Per verificare se un grafo non orientato è bipartito

Articoli interessanti...