In der Informatik sind der Algorithmus von Floyd-Warshall (auch bekannt als der Algorithmus von Floyd, Algorithmus von Roy-Warshall, Algorithmus von Roy-Floyd oder der WFI Algorithmus) ein Graph-Analyse-Algorithmus, um kürzeste Pfade in einem belasteten Graphen (mit positiven oder negativen Rand-Gewichten) zu finden und um auch transitiven Verschluss einer Beziehung R zu finden. Eine einzelne Ausführung des Algorithmus wird die Längen (summierte Gewichte) der kürzesten Pfade zwischen allen Paaren von Scheitelpunkten finden, obwohl es Details der Pfade selbst nicht zurückgibt. Der Algorithmus ist ein Beispiel der dynamischen Programmierung. Es wurde in seiner zurzeit anerkannten Form von Robert Floyd 1962 veröffentlicht. Jedoch ist es im Wesentlichen dasselbe als Algorithmen, die vorher von Bernard Roy 1959 und auch durch Stephen Warshall 1962 veröffentlicht sind, für den transitiven Verschluss eines Graphen zu finden.

Algorithmus

Der Algorithmus von Floyd-Warshall vergleicht alle möglichen Pfade durch den Graphen zwischen jedem Paar von Scheitelpunkten. Es ist im Stande, das mit nur Θ (| V) Vergleiche in einem Graphen zu tun. Das ist das bemerkenswerte Betrachten, dass es bis zu Ω (| V) Ränder im Graphen geben kann, und jede Kombination von Rändern geprüft wird. Es tut so durch die zusätzliche Besserung einer Schätzung den kürzesten Pfad zwischen zwei Scheitelpunkten, bis die Schätzung optimal ist.

Denken Sie einen Graphen G mit Scheitelpunkten V, jedem numerierten 1 durch N. Denken Sie weiter eine Funktion shortestPath (ich, j, k), der den kürzestmöglichen Pfad von mir bis j das Verwenden von Scheitelpunkten nur vom Satz {1,2..., k} zurückgibt, weil Zwischenglied entlang dem Weg hinweist. Jetzt, in Anbetracht dieser Funktion, ist unsere Absicht, den kürzesten Pfad von jedem mich zu jedem j das Verwenden nur von Scheitelpunkten 1 zu k + 1 zu finden.

Es gibt zwei Kandidaten für jeden dieser Pfade: Irgendein der wahre kürzeste Pfad verwendet nur Scheitelpunkte im Satz {1..., k}; oder dort besteht ein Pfad, der von mir bis k + 1, dann von k + 1 zu j geht, der besser ist. Wir wissen, dass der beste Pfad von mir bis j, der nur Scheitelpunkte 1 durch k verwendet, durch shortestPath (ich, j, k) definiert werde, und es dass klar ist, wenn es einen besseren Pfad von mir bis k + 1 zu j gäbe, dann würde die Länge dieses Pfads die Verkettung des kürzesten Pfads von mir bis k + 1 (das Verwenden von Scheitelpunkten in {1..., k}) und des kürzesten Pfads von k + 1 zu j sein (auch Scheitelpunkte in {1..., k} verwendend).

Wenn das Gewicht des Randes zwischen Scheitelpunkten i und j ist, können wir shortestPath (ich, j, k) in Bezug auf die folgende rekursive Formel definieren: Der Grundfall ist

:

und der rekursive Fall ist

:

Diese Formel ist das Herz des Algorithmus von Floyd-Warshall. Der Algorithmus arbeitet durch die erste Computerwissenschaft shortestPath (ich, j, k) für alle (ich, j) Paare für k = 1, dann k = 2, usw. Dieser Prozess geht weiter bis k = n, und haben wir den kürzesten Pfad für alle (ich, j) Paare gefunden, die irgendwelche Zwischenscheitelpunkte verwenden.

Pseudocode

Günstig, wenn man den kth Fall berechnet, kann man die Information überschreiben, die von der Berechnung von k &minus gespart ist; 1. Das bedeutet, dass der Algorithmus quadratisches Gedächtnis verwendet. Achten Sie darauf, die Initialisierungsbedingungen zu bemerken:

1/* Nehmen eine Funktion edgeCost An (ich, j), der die Kosten des Randes von mir bis j zurückgibt

2 (Unendlichkeit, wenn es niemanden gibt).

3 nehmen Auch an, dass n die Zahl von Scheitelpunkten und edgeCost (ich, i) = 0 ist

4 * /

5

6 int Pfad [] [];

7/* Eine 2-dimensionale Matrix. An jedem Schritt im Algorithmus Pfad bin [ich] [j] der kürzeste Pfad

8 von mir bis j, der Zwischenscheitelpunkte (1..k−1) verwendet. Jeder Pfad werde [ich] [j] zu initialisiert

9 edgeCost (ich, j).

10 * /

11

12 Verfahren FloydWarshall

13 für k: = 1 zu n

14 weil ich: = 1 zu n

15 für j: = 1 zu n

16 Pfad [ich] [j] = Minute (Pfad [ich] [j], Pfad [ich] [k] +path [k] [j]);

Verhalten mit negativen Zyklen

Ein negativer Zyklus ist ein Zyklus, dessen Ränder zu einem negativen Wert resümieren. Zwischen jedem Paar von Scheitelpunkten, die einen Teil eines negativen Zyklus bilden, ist der kürzeste Pfad nicht bestimmt, weil der Pfad willkürlich negativ sein kann. Für die numerisch bedeutungsvolle Produktion nimmt der Algorithmus von Floyd-Warshall an, dass es keine negativen Zyklen gibt. Dennoch, wenn es negative Zyklen gibt, kann der Algorithmus von Floyd-Warshall verwendet werden, um sie zu entdecken. Die Intuition ist wie folgt:

• Der Algorithmus von Floyd-Warshall revidiert wiederholend Pfad-Längen zwischen allen Paaren von Scheitelpunkten (ich, j), einschließlich wo ich = j;
• Am Anfang ist die Länge des Pfads (ich, i) Null;
• Ein Pfad {(ich, k), (k, i)} kann nur das übertreffen, wenn er Länge weniger hat als Null, d. h. einen negativen Zyklus anzeigt;
• So, nach dem Algorithmus, (ich, i) wird negativ sein, wenn dort ein Pfad der negativen Länge davon besteht, bewege mir mich zu mir rückwärts.

Folglich, um negative Zyklen mit dem Algorithmus von Floyd-Warshall zu entdecken, kann man die Diagonale der Pfad-Matrix untersuchen, und die Anwesenheit einer negativen Zahl zeigt an, dass der Graph mindestens einen negativen Zyklus enthält. Offensichtlich in einem ungeleiteten Graphen schafft ein negativer Rand einen negativen Zyklus (d. h., ein geschlossener Spaziergang) das Beteiligen seiner Ereignis-Scheitelpunkte.

Pfad-Rekonstruktion

Der Algorithmus von Floyd-Warshall stellt normalerweise nur die Längen der Pfade zwischen allen Paaren von Scheitelpunkten zur Verfügung. Mit einfachen Modifizierungen ist es möglich, eine Methode zu schaffen, den wirklichen Pfad zwischen irgendwelchen zwei Endpunkt-Scheitelpunkten wieder aufzubauen. Während man dazu neigen kann, den wirklichen Pfad von jedem Scheitelpunkt bis einander Scheitelpunkt zu versorgen, ist das, und tatsächlich nicht notwendig, ist in Bezug auf das Gedächtnis sehr kostspielig. Für jeden Scheitelpunkt versorgt ein Bedürfnis nur die Information über den höchsten Index-Zwischenscheitelpunkt, den man durchgehen muss, wenn man an einem gegebenem Scheitelpunkt enden möchte. Deshalb kann Information, um alle Pfade wieder aufzubauen, in einer einzelnen N×N Matrix 'als nächstes' versorgt werden, wo als nächstes [ich] [j] den höchsten Index-Scheitelpunkt vertrete, muss man durch reisen, wenn man vorhat, den kürzesten Pfad von mir bis j zu nehmen. Das Einführen solch eines Schemas ist als trivial, wenn ein neuer kürzester Pfad zwischen zwei Scheitelpunkten gefunden wird, wird die Matrix, die die Pfade enthält, aktualisiert. Die folgende Matrix wird zusammen mit der solcher Pfad-Matrix aktualisiert, dass bei der Vollziehung beide Tische abgeschlossen und genau sind, und irgendwelche Einträge, die im Pfad-Tisch unendlich sind, im folgenden Tisch ungültig sein werden. Der Pfad von bin mir bis j dann Pfad von mir bis folgenden [ich] [j], der vom Pfad vom folgenden [ich] [j] zu j gefolgt ist. Diese zwei kürzeren Pfade werden rekursiv bestimmt. Dieser modifizierte Algorithmus läuft mit derselben Kompliziertheit der Zeit und Raums wie der unmodifizierte Algorithmus.

1 Verfahren FloydWarshallWithPathReconstruction

2 für k: = 1 zu n

3 weil ich: = 1 zu n

4 für j: = 1 zu n

5, wenn Pfad [ich] [k] + Pfad [k] [j] shortestPath (ich, j, k) (für alles ich und j) von denjenigen von shortestPath (ich, j, k1) 2n Operationen verlangt. Da wir mit shortestPath (ich, j, 0) = edgeCost (ich, j) beginnen und die Folge von n matrices shortestPath (ich, j, 1), shortestPath (ich, j, 2), …, shortestPath schätzen (ich, j, n), ist die Gesamtzahl von verwendeten Operationen n · 2n = 2n. Deshalb ist die Kompliziertheit des Algorithmus Θ (n).

Anwendungen und Generalisationen

Der Algorithmus von Floyd-Warshall kann verwendet werden, um die folgenden Probleme, unter anderen zu beheben:

• Kürzeste Pfade in geleiteten Graphen (der Algorithmus von Floyd).
• Transitiver Verschluss von geleiteten Graphen (der Algorithmus von Warshall). In der ursprünglichen Formulierung von Warshall des Algorithmus ist der Graph unbelastet und durch eine Angrenzen-Matrix von Boolean vertreten. Dann wird die Hinzufügungsoperation durch die logische Verbindung (UND) und die minimale Operation durch die logische Trennung ersetzt (ODER).
• Die Entdeckung eines regelmäßigen Ausdrucks, der die regelmäßige Sprache anzeigt, die durch einen begrenzten Automaten (der Algorithmus von Kleene) akzeptiert ist
• Inversion von echtem matrices (Algorithmus von Gauss-Jordan)
• Optimale Routenplanung. In dieser Anwendung interessiert man sich für die Entdeckung des Pfads mit dem maximalen Fluss zwischen zwei Scheitelpunkten. Das bedeutet, dass, anstatt Minima als im Pseudocode oben zu nehmen, man stattdessen Maxima nimmt. Die Rand-Gewichte vertreten geheftete Einschränkungen auf den Fluss. Pfad-Gewichte vertreten Engpässe; so wird die Hinzufügungsoperation oben durch die minimale Operation ersetzt.
• Die Prüfung, ob ein ungeleiteter Graph zweiteilig ist.
• Schnelle Berechnung von Bahnbrecher-Netzen.
• Breiteste Bandbreite-Pfade der Pfade/Maximums

Durchführungen

Durchführungen sind für viele Programmiersprachen verfügbar.

• Für C ++, in der Zunahme:: Graph-Bibliothek
• Für C#, an QuickGraph
• Für Clojure, an paste.lisp.org
• Für Java, in der Apachen-Unterhaus-Graph-Bibliothek, oder an Algowiki
• Für MATLAB, im Matlab_bgl Paket
• Für Perl, im Graph-Modul
• Für PHP, auf der Seite und PL/pgSQL, auf der Seite an der Mikroschale
• Für die Pythonschlange, in der Bibliothek von NetworkX
• Für R, im Paket e1017
• Für den Rubin, in der Schrift

Siehe auch

• Der Algorithmus von Dijkstra, ein Algorithmus, um einzelne Quelle kürzeste Pfade in einer einschränkenderen Klasse von Eingängen, Graphen zu finden, in denen alle Rand-Gewichte nichtnegativer sind
• Der Algorithmus von Johnson, ein Algorithmus, für dasselbe Problem wie der Algorithmus von Floyd-Warshall, alle Paare kürzeste Pfade in Graphen mit einigen negativen Rand-Gewichten zu beheben. Im Vergleich zum Algorithmus von Floyd-Warshall ist der Algorithmus von Johnson für spärliche Graphen effizienter.
• Abschnitt 26.2, "Der Algorithmus von Floyd-Warshall", Seiten 558-565;
• Abschnitt 26.4, "Ein allgemeines Fachwerk, um Pfad-Probleme in geleiteten Graphen", Seiten 570-576 zu beheben.

Links

• Interaktiver Zeichentrickfilm des Algorithmus von Floyd-Warshall
• Der Algorithmus von Floyd-Warshall in C#, als ein Teil von QuickGraph
• Vergegenwärtigung des Algorithmus von Floyd