Floyd-Warshall algoritme

I denne veiledningen vil du lære hvordan floyd-warshall-algoritmen fungerer. Du finner også arbeidseksempler på floyd-warshall-algoritme i C, C ++, Java og Python.

Floyd-Warshall Algoritme er en algoritme for å finne den korteste stien mellom alle toppunktparene i en vektet graf. Denne algoritmen fungerer for både de rettede og ikke-rettet vektede grafer. Men det fungerer ikke for grafene med negative sykluser (hvor summen av kantene i en syklus er negativ).

En vektet graf er en graf der hver kant har en numerisk verdi knyttet til seg.

Floyd-Warhshall-algoritme kalles også som Floyds algoritme, Roy-Floyd-algoritme, Roy-Warshall-algoritme eller WFI-algoritme.

Denne algoritmen følger den dynamiske programmeringsmetoden for å finne de korteste stiene.

Hvordan fungerer Floyd-Warshall Algorithm?

La den gitte grafen være:

Innledende graf

Følg trinnene nedenfor for å finne den korteste stien mellom alle parene i toppunktene.

  1. Lag en matrise med dimensjon der n er antall hjørner. Raden og kolonnen er indeksert som henholdsvis i og j. i og j er toppunktene i grafen. Hver celle A (i) (j) er fylt med avstanden fra toppunktet til toppunktet. Hvis det ikke er noen sti fra toppunkt til toppunkt, blir cellen igjen som uendelig. Fyll hver celle med avstanden mellom ith og jth toppunktA0n*n
    ithjthithjth
  2. Lag nå en matrise ved hjelp av matrise . Elementene i første kolonne og første rad blir liggende som de er. De resterende cellene fylles ut på følgende måte. La k være mellompunktet i den korteste veien fra kilde til destinasjon. I dette trinnet er k det første toppunktet. er fylt med . Det vil si at hvis den direkte avstanden fra kilden til destinasjonen er større enn banen gjennom toppunktet k, blir cellen fylt med . I dette trinnet er k toppunkt 1. Vi beregner avstanden fra kildepunktet til bestemmelsespunktet gjennom dette toppunktet k. Beregn avstanden fra kildepunktet til bestemmelsespunktet gjennom dette toppunktet k For eksempel: 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)Den direkte avstanden fra toppunktet 2 til 4 er 4 og summen av avstanden fra toppunktet 2 til 4 gjennom toppunktet (f.eks. Fra toppunktet 2 til 1 og fra toppunktet 1 til 4) er 7. Da 4 < 7, er fylt med fire.A0(2, 4)
  3. Tilsvarende er opprettet ved hjelp av . Elementene i den andre kolonnen og den andre raden er igjen som de er. I dette trinnet er k det andre toppunktet (dvs. toppunkt 2). De resterende trinnene er de samme som i trinn 2 . Beregn avstanden fra kildepunktet til bestemmelsespunktet gjennom dette toppunktet 2A2A3
  4. Tilsvarende, og er også opprettet. Beregn avstanden fra kildepunktet til destinasjonspunktet gjennom dette toppunktet 3 Beregn avstanden fra kildepunktet til destinasjonspunktet gjennom dette toppunktet 4A3A4
  5. A4 gir den korteste banen mellom hvert par av toppunktene.

Floyd-Warshall algoritme

n = antall hjørner A = matrise av dimensjonen n * n for k = 1 til n for i = 1 til n for j = 1 til n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) retur A

Python, Java og C / C ++ eksempler

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

Tidskompleksitet

Det er tre løkker. Hver sløyfe har konstante kompleksiteter. Så tidskompleksiteten til Floyd-Warshall-algoritmen er .O(n3)

Romkompleksitet

Plasskompleksiteten til Floyd-Warshall-algoritmen er .O(n2)

Floyd Warshall algoritmeapplikasjoner

  • For å finne den korteste veien er en rettet graf
  • For å finne den transitive lukkingen av rettet graf
  • For å finne inversjonen av virkelige matriser
  • For å teste om en ikke-rettet graf er tosidig

Interessante artikler...