Floyd-Warshall algoritm

I denna handledning lär du dig hur floyd-warshall-algoritmen fungerar. Dessutom hittar du arbetsexempel på floyd-warshall-algoritm i C, C ++, Java och Python.

Floyd-Warshall Algorithm är en algoritm för att hitta den kortaste vägen mellan alla par av hörn i ett viktat diagram. Denna algoritm fungerar för både riktade och oriktade viktade grafer. Men det fungerar inte för graferna med negativa cykler (där summan av kanterna i en cykel är negativ).

Ett viktat diagram är ett diagram där varje kant har ett numeriskt värde associerat med sig.

Floyd-Warhshall-algoritm kallas också för Floyds algoritm, Roy-Floyd-algoritm, Roy-Warshall-algoritm eller WFI-algoritm.

Denna algoritm följer den dynamiska programmeringsmetoden för att hitta de kortaste vägarna.

Hur fungerar Floyd-Warshall Algorithm?

Låt den givna grafen vara:

Inledande diagram

Följ stegen nedan för att hitta den kortaste vägen mellan alla hörnpar.

  1. Skapa en matris med dimension där n är antalet hörnpunkter. Raden och kolumnen indexeras som i respektive j. i och j är kurvorna i diagrammet. Varje cell A (i) (j) är fylld med avståndet från toppunkt till toppunkt. Om det inte finns någon väg från topp till topp, lämnas cellen som oändlighet. Fyll varje cell med avståndet mellan I och Jth toppunktA0n*n
    ithjthithjth
  2. Skapa nu en matris med hjälp av matris . Elementen i den första kolumnen och den första raden lämnas som de är. De återstående cellerna fylls på följande sätt. Låt k vara det mellanliggande toppunktet på den kortaste vägen från källa till destination. I detta steg är k det första toppunktet. är fylld med . Det vill säga om det direkta avståndet från källan till destinationen är större än vägen genom toppunkten k, fylls cellen med . I detta steg är k vertex 1. Vi beräknar avståndet från källpunkten till destinationspunkten genom detta toppunkt k. Beräkna avståndet från källpunkten till destinationspunkten genom denna toppunkt k Till exempel: förA1A0
    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), Är den direkta avståndet från vertex 2 till 4 4 och summan av avståndet från vertex 2 till 4 genom vertex (dvs. Från vertex 2 till 1 och från vertex 1 till 4) är 7. Eftersom 4 < 7, är fylld med fyra.A0(2, 4)
  3. På samma sätt skapas med . Elementen i den andra kolumnen och den andra raden lämnas som de är. I detta steg är k den andra toppunkten (dvs. toppunkt 2). De återstående stegen är desamma som i steg 2 . Beräkna avståndet från källpunkten till destinationspunkten genom denna toppunkt 2A2A3
  4. På samma sätt och skapas också. Beräkna avståndet från källpunkten till destinationspunkten genom denna toppunkt 3 Beräkna avståndet från källpunkten till destinationspunkten genom denna toppunkt 4A3A4
  5. A4 ger den kortaste vägen mellan varje par av hörn.

Floyd-Warshall algoritm

n = antal hörnpunkter A = matris för dimensionen n * n för k = 1 till n för i = 1 till n för j = 1 till 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 och C / C ++ exempel

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

Tidskomplexitet

Det finns tre öglor. Varje slinga har konstant komplexitet. Så tidskomplexiteten hos Floyd-Warshall-algoritmen är .O(n3)

Rymdkomplexitet

Rymdkomplexiteten hos Floyd-Warshall-algoritmen är .O(n2)

Floyd Warshall algoritmapplikationer

  • Att hitta den kortaste vägen är en riktad graf
  • För att hitta den transitiva stängningen av riktade grafer
  • Att hitta inversionen av riktiga matriser
  • För att testa om en icke-riktad graf är bipartit

Intressanta artiklar...