Floyd-Warshall-Algorithmus

In diesem Tutorial erfahren Sie, wie der Floyd-Warshall-Algorithmus funktioniert. Außerdem finden Sie Arbeitsbeispiele für den Floyd-Warshall-Algorithmus in C, C ++, Java und Python.

Der Floyd-Warshall-Algorithmus ist ein Algorithmus zum Ermitteln des kürzesten Pfades zwischen allen Scheitelpunktpaaren in einem gewichteten Graphen. Dieser Algorithmus funktioniert sowohl für gerichtete als auch für ungerichtete gewichtete Graphen. Dies funktioniert jedoch nicht für Diagramme mit negativen Zyklen (bei denen die Summe der Kanten in einem Zyklus negativ ist).

Ein gewichtetes Diagramm ist ein Diagramm, dem jeder Kante ein numerischer Wert zugeordnet ist.

Der Floyd-Warhshall-Algorithmus wird auch als Floyd-Algorithmus, Roy-Floyd-Algorithmus, Roy-Warshall-Algorithmus oder WFI-Algorithmus bezeichnet.

Dieser Algorithmus folgt dem dynamischen Programmieransatz, um die kürzesten Wege zu finden.

Wie funktioniert der Floyd-Warshall-Algorithmus?

Der gegebene Graph sei:

Anfangsgrafik

Führen Sie die folgenden Schritte aus, um den kürzesten Pfad zwischen allen Scheitelpunktpaaren zu finden.

  1. Erstellen Sie eine Dimensionsmatrix, wobei n die Anzahl der Scheitelpunkte ist. Die Zeile und die Spalte sind als i bzw. j indiziert. i und j sind die Eckpunkte des Graphen. Jede Zelle A (i) (j) ist mit dem Abstand vom Scheitelpunkt zum Scheitelpunkt gefüllt . Wenn es keinen Pfad von Scheitelpunkt zu Scheitelpunkt gibt, bleibt die Zelle als unendlich. Füllen Sie jede Zelle mit dem Abstand zwischen dem i-ten und dem j-ten ScheitelpunktA0n*n
    ithjthithjth
  2. Erstellen Sie nun eine Matrix mit Matrix . Die Elemente in der ersten Spalte und der ersten Zeile bleiben unverändert. Die verbleibenden Zellen werden folgendermaßen gefüllt. Sei k der Zwischenscheitelpunkt auf dem kürzesten Weg von der Quelle zum Ziel. In diesem Schritt ist k der erste Scheitelpunkt. ist gefüllt mit . Das heißt, wenn der direkte Abstand von der Quelle zum Ziel größer ist als der Pfad durch den Scheitelpunkt k, dann ist die Zelle mit gefüllt . In diesem Schritt ist k Scheitelpunkt 1. Wir berechnen den Abstand vom Quellscheitelpunkt zum Zielscheitelpunkt durch diesen Scheitelpunkt k. Berechnen Sie den Abstand vom Quellscheitelpunkt zum Zielscheitelpunkt über diesen Scheitelpunkt k Beispiel: 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)Der direkte Abstand von Scheitelpunkt 2 bis 4 ist 4 und die Summe aus dem Abstand vom Scheitel 2 bis 4 durch Scheitel (dh. Von Knoten 2 zu 1 und von Knoten 1 bis 4) ist 7. Da 4 < 7, ist mit 4 gefüllt.A0(2, 4)
  3. Ebenso wird mit erstellt . Die Elemente in der zweiten Spalte und der zweiten Zeile bleiben unverändert. In diesem Schritt ist k der zweite Scheitelpunkt (dh Scheitelpunkt 2). Die verbleibenden Schritte sind die gleichen wie in Schritt 2 . Berechnen Sie den Abstand vom Quellscheitelpunkt zum Zielscheitelpunkt durch diesen Scheitelpunkt 2A2A3
  4. Ebenso und wird auch erstellt. Berechnen Sie die Entfernung vom Quellscheitelpunkt zum Zielscheitelpunkt durch diesen Scheitelpunkt 3 Berechnen Sie die Entfernung vom Quellscheitelpunkt zum Zielscheitelpunkt durch diesen Scheitelpunkt 4A3A4
  5. A4 gibt den kürzesten Weg zwischen jedem Scheitelpunktpaar an.

Floyd-Warshall-Algorithmus

n = Anzahl der Eckpunkte A = Matrix der Dimension n * n für k = 1 bis n für i = 1 bis n für j = 1 bis n A k (i, j) = min (A k - 1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) geben A zurück

Beispiele für Python, Java und 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); )

Komplexität des Floyd Warshall-Algorithmus

Zeitliche Komplexität

Es gibt drei Schleifen. Jede Schleife hat konstante Komplexität. Die zeitliche Komplexität des Floyd-Warshall-Algorithmus ist also .O(n3)

Raumkomplexität

Die räumliche Komplexität des Floyd-Warshall-Algorithmus ist .O(n2)

Floyd Warshall-Algorithmus-Anwendungen

  • Den kürzesten Weg zu finden, ist ein gerichteter Graph
  • Den transitiven Abschluss gerichteter Graphen finden
  • Um die Inversion von reellen Matrizen zu finden
  • Zum Testen, ob ein ungerichteter Graph zweiteilig ist

Interessante Beiträge...