Floyd-Warshall algoritme

I denne vejledning lærer du, hvordan floyd-warshall-algoritmen fungerer. Du finder også arbejdseksempler på floyd-warshall-algoritme i C, C ++, Java og Python.

Floyd-Warshall Algoritme er en algoritme til at finde den korteste sti mellem alle par af hjørner i en vægtet graf. Denne algoritme fungerer for både de rettet og ikke-rettet vægtede grafer. Men det fungerer ikke for graferne med negative cyklusser (hvor summen af ​​kanterne i en cyklus er negativ).

En vægtet graf er en graf, hvor hver kant har en numerisk værdi tilknyttet.

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

Denne algoritme følger den dynamiske programmeringsmetode for at finde de korteste stier.

Hvordan fungerer Floyd-Warshall algoritme?

Lad den givne graf være:

Indledende graf

Følg trinene nedenfor for at finde den korteste sti mellem alle parene i hjørnerne.

  1. Opret en matrix med dimension, hvor n er antallet af hjørner. Rækken og kolonnen indekseres som henholdsvis i og j. i og j er hjørnerne i grafen. Hver celle A (i) (j) er fyldt med afstanden fra toppunktet til toppunktet. Hvis der ikke er nogen sti fra toppunkt til toppunkt, efterlades cellen som uendelig. Fyld hver celle med afstanden mellem ith og jth toppunktA0n*n
    ithjthithjth
  2. Opret nu en matrix ved hjælp af matrix . Elementerne i den første kolonne og den første række er som de er. De resterende celler udfyldes på følgende måde. Lad k være det mellemste toppunkt i den korteste sti fra kilde til destination. I dette trin er k det første toppunkt. er fyldt med . Det vil sige, at hvis den direkte afstand fra kilden til destinationen er større end stien gennem toppunktet k, er cellen fyldt med . I dette trin er k toppunkt 1. Vi beregner afstanden fra kildepunktet til destinationspunktet gennem dette toppunkt k. Beregn afstanden fra kildepunktet til destinationspunktet gennem dette toppunkt 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 afstand fra toppunktet 2 til 4 er 4, og summen af afstanden fra toppunktet 2 til 4 gennem toppunkt (dvs.. Fra stilling 2 til 1 og fra toppunktet 1 til 4) er 7. Da 4 < 7, fyldes med 4.A0(2, 4)
  3. Ligeledes oprettes ved hjælp af . Elementerne i anden kolonne og anden række er som de er. I dette trin er k det andet toppunkt (dvs. toppunkt 2). De resterende trin er de samme som i trin 2 . Beregn afstanden fra kildepunktet til destinationspunktet gennem dette toppunkt 2A2A3
  4. Tilsvarende og oprettes også. Beregn afstanden fra kildepunktet til destinationspunktet gennem dette toppunkt 3 Beregn afstanden fra kildepunktet til destinationspunktet gennem dette toppunkt 4A3A4
  5. A4 giver den korteste sti mellem hvert par af hjørner.

Floyd-Warshall algoritme

n = antal hjørner A = matrix for dimension 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)) returnerer 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 algoritmekompleksitet

Tidskompleksitet

Der er tre sløjfer. Hver sløjfe har konstante kompleksiteter. Så tidskompleksiteten af ​​Floyd-Warshall-algoritmen er .O(n3)

Rumkompleksitet

Rummets kompleksitet i Floyd-Warshall-algoritmen er .O(n2)

Floyd Warshall algoritme applikationer

  • At finde den korteste sti er en rettet graf
  • At finde den transitive lukning af rettet graf
  • At finde inversionen af ​​ægte matricer
  • Til test af, om en ikke-rettet graf er toparts

Interessante artikler...