algorithm
Floyd-Warshall-Algorithmus

Algorithmus für kürzesten Pfad aller Paare

Der Algorithmus von Floyd-Warshall dient zum Finden kürzester Pfade in einem gewichteten Diagramm mit positiven oder negativen Kantengewichten. Bei einer einzelnen Ausführung des Algorithmus werden die Längen (summierten Gewichtungen) der kürzesten Pfade zwischen allen Knotenpaaren ermittelt. Mit etwas Abweichung kann er den kürzesten Weg drucken und negative Zyklen in einem Diagramm erkennen. Floyd-Warshall ist ein Algorithmus zur dynamischen Programmierung.

Schauen wir uns ein Beispiel an. Wir werden den Algorithmus von Floyd-Warshall auf diese Grafik anwenden:

Als erstes nehmen wir zwei 2D-Matrizen. Dies sind Adjazenzmatrizen . Die Größe der Matrizen wird die Gesamtanzahl der Scheitelpunkte sein. Für unser Diagramm nehmen wir 4 * 4- Matrizen. Die Distanzmatrix speichert den bisher gefundenen Mindestabstand zwischen zwei Scheitelpunkten. Wenn sich für die Kanten zuerst eine Kante zwischen uv befindet und der Abstand / das Gewicht w ist , werden wir speichern: distance[u][v] = w . Für alle Kanten, die nicht existieren, setzen wir unendlich . Die Pfadmatrix dient zum Wiederherstellen eines Pfads mit minimalem Abstand zwischen zwei Scheitelpunkten. Wenn anfangs ein Pfad zwischen u und v ist , setzen wir path[u][v] = u . Dies bedeutet, der beste Weg, um von vertex-u zu vertex-v zu gelangen, ist die Verwendung der Kante, die v mit u verbindet . Wenn es keinen Pfad zwischen zwei Scheitelpunkten gibt, setzen wir dort N , um anzuzeigen, dass jetzt kein Pfad verfügbar ist. Die zwei Tabellen für unser Diagramm sehen folgendermaßen aus:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  6  |  15 |            |  1  |  N  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  | inf |  0  | -2  | inf |            |  2  |  N  |  N  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  | inf | inf |  0  |  2  |            |  3  |  N  |  N  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  | inf | inf |  0  |            |  4  |  4  |  N  |  N  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Da es keine Schleife gibt, werden die Diagonalen auf N gesetzt . Und der Abstand zum Scheitelpunkt selbst ist 0 .

Um den Floyd-Warshall-Algorithmus anzuwenden, wählen wir einen mittleren Scheitelpunkt k aus . Dann werden wir für jeden Knoten i prüfen, ob wir von i nach k und dann von k nach j gehen können , wobei j ein weiterer Knoten ist, und die Kosten für den Übergang von i nach j minimieren. Wenn der aktuelle Abstand [i] [j] größer ist als der Abstand [i] [k] + Abstand [k] [j] , setzen wir den Abstand [i] [j] gleich der Summe dieser beiden Abstände . Und der Pfad [i] [j] wird auf Pfad [k] [j] gesetzt , da es besser ist, von i nach k und dann von k nach j zu gehen . Alle Scheitelpunkte werden als k ausgewählt. Wir werden drei verschachtelte Schleifen haben: für k von 1 bis 4 gehen, i von 1 bis 4 und j von 1 bis 4 gehen gehe wir überprüfen gehen:

if distance[i][j] > distance[i][k] + distance[k][j]
    distance[i][j] := distance[i][k] + distance[k][j]
    path[i][j] := path[k][j]
end if

Im Grunde prüfen wir also, ob wir für jedes Scheitelpaar ein kürzeres Maß erreichen, wenn wir einen anderen Scheitelpunkt durchlaufen. Die Gesamtzahl der Operationen für unser Diagramm beträgt 4 * 4 * 4 = 64 . Das bedeutet, dass wir diese Prüfung 64- mal durchführen. Schauen wir uns einige davon an:

Wenn k = 1 , i = 2 und j = 3 ist , ist der Abstand [i] [j] -2 , was nicht größer ist als der Abstand [i] [k] + Abstand [k] [j] = -2 + 0 = -2 . So bleibt es unverändert. Wenn k = 1 , i = 4 und j = 2 ist , ist der Abstand [i] [j] = unendlich , was größer ist als der Abstand [i] [k] + Abstand [k] [j] = 1 + 3 = 4 . Also setzen wir Abstand [i] [j] = 4 und wir setzen Pfad [i] [j] = Pfad [k] [j] = 1 . Das bedeutet, um von Vertex-4 zu Vertex-2 zu gelangen , ist der Pfad 4-> 1-> 2 kürzer als der vorhandene Pfad. So bevölkern wir beide Matrizen. Die Berechnung für jeden Schritt wird hier angezeigt. Nachdem Sie die erforderlichen Änderungen vorgenommen haben, werden unsere Matrizen folgendermaßen aussehen:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  1  |  3  |            |  1  |  N  |  1  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  |  1  |  0  | -2  |  0  |            |  2  |  4  |  N  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  |  3  |  6  |  0  |  2  |            |  3  |  4  |  1  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  |  4  |  2  |  0  |            |  4  |  4  |  1  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Dies ist unsere kürzeste Entfernungsmatrix. Zum Beispiel ist der kürzeste Abstand von 1 bis 4 3 und der kürzeste Abstand zwischen 4 und 3 ist 2 . Unser Pseudo-Code lautet:

Procedure Floyd-Warshall(Graph):
for k from 1 to V     // V denotes the number of vertex
    for i from 1 to V
       for j from 1 to V
           if distance[i][j] > distance[i][k] + distance[k][j]
               distance[i][j] := distance[i][k] + distance[k][j]
               path[i][j] := path[k][j]
           end if
       end for
    end for
end for

Pfad drucken:

Um den Pfad auszudrucken, überprüfen wir die Pfadmatrix . Um den Pfad von u nach v zu drucken, beginnen wir mit Pfad [u] [v] . Wir setzen fort, v = Pfad [u] [v] zu ändern, bis wir Pfad [u] [v] = u finden und alle Werte von Pfad [u] [v] in einem Stapel schieben. Nachdem Sie u gefunden haben , drucken wir u und fangen an, Gegenstände aus dem Stapel zu werfen und zu drucken. Dies funktioniert , weil die Pfad - Matrix den Wert des Scheitelpunktes speichert , die den kürzesten Weg zu v von jedem anderen Knoten teilt. Der Pseudo-Code lautet:

Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
    S.push(Path[source][destination])
    destination := Path[source][destination]
end while
print -> source
while S is not empty
    print -> S.pop
end while

Suche nach einem negativen Kantenzyklus:

Um herauszufinden, ob es einen negativen Flankenzyklus gibt, müssen wir die Hauptdiagonale der Distanzmatrix überprüfen. Wenn ein Wert auf der Diagonale negativ ist, bedeutet dies, dass der Graph einen negativen Zyklus aufweist.

Komplexität:

Die Komplexität des Floyd-Warshall-Algorithmus ist O (V³) und die Raumkomplexität ist: O (V²) .