Floyd-Warshall-algoritme

In deze tutorial leer je hoe het floyd-warshall-algoritme werkt. Ook vindt u werkende voorbeelden van het floyd-warshall-algoritme in C, C ++, Java en Python.

Floyd-Warshall-algoritme is een algoritme voor het vinden van het kortste pad tussen alle paren hoekpunten in een gewogen grafiek. Dit algoritme werkt voor zowel de gerichte als de niet-gerichte gewogen grafieken. Maar het werkt niet voor de grafieken met negatieve cycli (waarbij de som van de randen in een cyclus negatief is).

Een gewogen grafiek is een grafiek waarin aan elke rand een numerieke waarde is gekoppeld.

Het Floyd-Warhshall-algoritme wordt ook wel het algoritme van Floyd, het Roy-Floyd-algoritme, het Roy-Warshall-algoritme of het WFI-algoritme genoemd.

Dit algoritme volgt de dynamische programmeerbenadering om de kortste paden te vinden.

Hoe werkt het Floyd-Warshall-algoritme?

Laat de gegeven grafiek zijn:

Eerste grafiek

Volg de onderstaande stappen om het kortste pad tussen alle paren hoekpunten te vinden.

  1. Maak een matrix van dimensies waarbij n het aantal hoekpunten is. De rij en de kolom worden respectievelijk geïndexeerd als i en j. i en j zijn de hoekpunten van de grafiek. Elke cel A (i) (j) is gevuld met de afstand van het hoekpunt tot het hoekpunt. Als er geen pad is van hoekpunt naar hoekpunt, blijft de cel oneindig. Vul elke cel met de afstand tussen de ith en de jde topA0n*n
    ithjthithjth
  2. Maak nu een matrix met behulp van matrix . De elementen in de eerste kolom en de eerste rij blijven zoals ze zijn. De overige cellen worden op de volgende manier gevuld. Laat k het tussenliggende hoekpunt zijn in het kortste pad van bron naar bestemming. In deze stap is k het eerste hoekpunt. is gevuld met . Dat wil zeggen, als de directe afstand van de bron naar de bestemming groter is dan het pad door het hoekpunt k, dan wordt de cel gevuld met . In deze stap is k hoekpunt 1. We berekenen de afstand van bronknooppunt tot bestemmingsknooppunt door dit hoekpunt k. Bereken de afstand van het bronknooppunt tot het bestemmingsknooppunt via dit hoekpunt k Bijvoorbeeld: 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), de directe afstand van hoekpunt 2 tot 4 is 4 en de som van de afstand van hoekpunt 2 tot 4 tot hoekpunt (dat wil zeggen van hoekpunt 2 tot 1 en van hoekpunt 1 tot 4) is 7. Aangezien 4 < 7, is gevuld met 4.A0(2, 4)
  3. Evenzo wordt gemaakt met . De elementen in de tweede kolom en de tweede rij blijven zoals ze zijn. In deze stap is k het tweede hoekpunt (dwz hoekpunt 2). De overige stappen zijn hetzelfde als in stap 2 . Bereken de afstand van het bronpunt tot het doelpunt door dit hoekpunt 2A2A3
  4. Evenzo, en wordt ook gemaakt. Bereken de afstand van het bronknooppunt tot het bestemmingsknooppunt via dit hoekpunt 3 Bereken de afstand van het bronknooppunt tot het bestemmingsknooppunt via dit hoekpunt 4A3A4
  5. A4 geeft het kortste pad tussen elk paar hoekpunten.

Floyd-Warshall-algoritme

n = aantal hoekpunten A = matrix van dimensie n * n voor k = 1 tot n voor i = 1 tot n voor j = 1 tot n A k (i, j) = min (A k-1 (i, j) A k-1 (i, k) + A k-1 (k, j)) geeft A terug

Python, Java en C / C ++ voorbeelden

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); )

Complexiteit van het Floyd Warshall-algoritme

Tijdscomplexiteit

Er zijn drie lussen. Elke lus heeft constante complexiteit. Dus de tijdcomplexiteit van het Floyd-Warshall-algoritme is .O(n3)

Complexiteit van de ruimte

De ruimtecomplexiteit van het Floyd-Warshall-algoritme is .O(n2)

Floyd Warshall-algoritme-toepassingen

  • Om het kortste pad te vinden, is een gerichte grafiek
  • Om de transitieve sluiting van gerichte grafieken te vinden
  • Om de inversie van echte matrices te vinden
  • Om te testen of een niet-gerichte graaf tweeledig is

Interessante artikelen...