Floyd-Warshall-Algorithmus - Floyd–Warshall algorithm

Floyd-Warshall-Algorithmus

Klasse	Kürzeste-Weg-Problem mit allen Paaren (für gewichtete Graphen)
Datenstruktur	Graph
Worst-Case- Leistung	${\displaystyle \Theta (|V|^{3})}$
Best-Case- Leistung	${\displaystyle \Theta (|V|^{3})}$
Durchschnittliche Leistung	${\displaystyle \Theta (|V|^{3})}$
Raumkomplexität im schlimmsten Fall	${\displaystyle \Theta (|V|^{2})}$

In der Informatik ist der Floyd-Warshall-Algorithmus (auch bekannt als Floyd-Algorithmus , Roy-Warshall-Algorithmus , Roy-Floyd-Algorithmus oder WFI-Algorithmus ) ein Algorithmus zum Finden kürzester Pfade in einem gerichtet gewichteten Graphen mit positiver oder negativer Kante Gewichte (aber ohne negative Zyklen). Eine einzige Ausführung des Algorithmus wird die Längen (aufsummierte Gewichte) der kürzesten Pfade zwischen allen Scheitelpunktpaaren finden. Obwohl keine Details der Pfade selbst zurückgegeben werden, ist es möglich, die Pfade mit einfachen Modifikationen des Algorithmus zu rekonstruieren. Versionen des Algorithmus können auch verwendet werden, um den transitiven Abschluss einer Relation zu finden , oder (in Verbindung mit dem Schulze-Voting-System ) breiteste Pfade zwischen allen Knotenpaaren in einem gewichteten Graphen. ${\displaystyle R}$

Geschichte und Namensgebung

Der Floyd-Warshall-Algorithmus ist ein Beispiel für dynamische Programmierung und wurde in seiner derzeit anerkannten Form von Robert Floyd im Jahr 1962 veröffentlicht. Er ist jedoch im Wesentlichen der gleiche wie die Algorithmen, die zuvor von Bernard Roy im Jahr 1959 und auch von Stephen Warshall im Jahr 1962 veröffentlicht wurden den transitiven Abschluss eines Graphen zu finden und ist eng verwandt mit Kleenes Algorithmus (veröffentlicht 1956) zur Umwandlung eines deterministischen endlichen Automaten in einen regulären Ausdruck . Die moderne Formulierung des Algorithmus als drei verschachtelte for-Schleifen wurde erstmals 1962 von Peter Ingerman beschrieben.

Algorithmus

Der Floyd-Warshall-Algorithmus vergleicht alle möglichen Pfade durch den Graphen zwischen jedem Scheitelpunktpaar. Es ist in der Lage, dies mit Vergleichen in einem Graphen zu tun , auch wenn es bis zu Kanten im Graphen geben kann, und jede Kombination von Kanten wird getestet. Dies geschieht durch inkrementelles Verbessern einer Schätzung auf dem kürzesten Pfad zwischen zwei Scheitelpunkten, bis die Schätzung optimal ist. ${\displaystyle \Theta (|V|^{3})}$${\displaystyle \Omega (|V|^{2})}$

Betrachten Sie einen Graphen mit Scheitelpunkten, die von 1 bis nummeriert sind  . Betrachten Sie außerdem eine Funktion , die den kürzestmöglichen Weg von zu zurückgibt , wobei nur Scheitelpunkte aus der Menge als Zwischenpunkte auf dem Weg verwendet werden. Angesichts dieser Funktion ist es unser Ziel, den kürzesten Weg von jedem zu jedem unter Verwendung eines beliebigen Knotens in zu finden . ${\displaystyle G}$${\displaystyle V}$${\displaystyle N}$${\displaystyle \mathrm {shortestPath} (i,j,k)}$${\displaystyle i}$${\displaystyle j}$${\displaystyle \{1,2,\ldots,k\}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle \{1,2,\ldots,N\}}$

Für jedes dieser Scheitelpunktpaare könnte dies entweder sein ${\displaystyle \mathrm {shortestPath} (i,j,k)}$

(1) ein Pfad, der nicht durchläuft (verwendet nur Scheitelpunkte in der Menge .)${\displaystyle k}$${\displaystyle \{1,\ldots,k-1\}}$

oder

(2) ein Pfad, der durchgeht (von bis und dann von bis , beide nur mit Zwischenknoten in  )${\displaystyle k}$${\displaystyle i}$${\displaystyle k}$${\displaystyle k}$${\displaystyle j}$${\displaystyle \{1,\ldots,k-1\}}$

Wir wissen, dass der beste Pfad von nach , der nur Scheitelpunkte durch verwendet, durch definiert wird , und es ist klar, dass, wenn es einen besseren Pfad von nach nach gäbe, die Länge dieses Pfads die Verkettung des kürzesten Pfads von nach wäre (nur mit Zwischenscheitelpunkten in ) und dem kürzesten Weg von nach (nur mit Zwischenscheitelpunkten in  ). ${\displaystyle i}$${\displaystyle j}$${\displaystyle 1}$${\displaystyle k-1}$${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$${\displaystyle i}$${\displaystyle k}$${\displaystyle j}$${\displaystyle i}$${\displaystyle k}$${\displaystyle \{1,\ldots,k-1\}}$${\displaystyle k}$${\displaystyle j}$${\displaystyle \{1,\ldots,k-1\}}$

Wenn das Gewicht der Kante zwischen den Ecken und ist , können wir mit der folgenden rekursiven Formel definieren: Der Basisfall ist ${\displaystyle w(i,j)}$${\displaystyle i}$${\displaystyle j}$${\displaystyle \mathrm {shortestPath} (i,j,k)}$

${\displaystyle \mathrm {shortestPath} (i,j,0)=w(i,j)}$

und der rekursive Fall ist

${\displaystyle \mathrm {shortestPath} (i,j,k)=}$

${\displaystyle \mathrm {min} {\Big (}\mathrm {shortestPath} (i,j,k-1),}$

${\displaystyle \mathrm {shortestPath} (i,k,k-1)+\mathrm {shortestPath} (k,j,k-1){\Big)}}$.

Diese Formel ist das Herzstück des Floyd-Warshall-Algorithmus. Der Algorithmus arbeitet, indem er zuerst für alle Paare für , dann und so weiter berechnet . Dieser Prozess wird fortgesetzt bis , und wir haben den kürzesten Weg für alle Paare unter Verwendung von Zwischenknoten gefunden. Pseudocode für diese Basisversion folgt: ${\displaystyle \mathrm {shortestPath} (i,j,k)}$${\displaystyle (i,j)}$${\displaystyle k=1}$${\displaystyle k=2}$${\displaystyle k=N}$${\displaystyle (i,j)}$

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j] 
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if

Beispiel

Der obige Algorithmus wird in der Grafik links unten ausgeführt:

Vor der ersten Rekursion der äußeren Schleife, oben mit k = 0 bezeichnet , entsprechen die einzigen bekannten Pfade den einzelnen Kanten im Graphen. Bei k = 1 werden Pfade gefunden, die durch die Ecke 1 gehen: insbesondere wird der Pfad [2,1,3] gefunden, der den Pfad [2,3] ersetzt, der weniger Kanten hat, aber länger ist (in Bezug auf das Gewicht ). Bei k = 2 werden Pfade gefunden, die durch die Ecken {1,2} gehen. Die roten und blauen Kästchen zeigen, wie der Pfad [4,2,1,3] aus den beiden bekannten Pfaden [4,2] und [2,1,3] zusammengesetzt wird, die in früheren Iterationen angetroffen wurden, mit 2 im Schnittpunkt. Der Pfad [4,2,3] wird nicht berücksichtigt, da [2,1,3] der kürzeste bisher gefundene Pfad von 2 nach 3 ist. Bei k = 3 gehen Pfade durch die Knoten {1,2,3} gefunden werden. Schließlich werden bei k = 4 alle kürzesten Wege gefunden.

Die Distanzmatrix bei jeder Iteration von k , mit den aktualisierten Distanzen in Fettdruck , ist:

Verhalten bei negativen Zyklen

Ein negativer Zyklus ist ein Zyklus, dessen Flanken einen negativen Wert ergeben. Es gibt keinen kürzesten Weg zwischen einem Paar von Scheitelpunkten , die Teil eines negativen Zyklus sind, da die Weglängen von bis beliebig klein (negativ) sein können. Für eine numerisch sinnvolle Ausgabe geht der Floyd-Warshall-Algorithmus davon aus, dass es keine negativen Zyklen gibt. Wenn es dennoch negative Zyklen gibt, kann der Floyd-Warshall-Algorithmus verwendet werden, um diese zu erkennen. Die Intuition ist wie folgt: ${\displaystyle i}$${\displaystyle j}$${\displaystyle i}$${\displaystyle j}$

• Der Floyd-Warshall-Algorithmus revidiert iterativ die Pfadlängen zwischen allen Scheitelpunktpaaren , einschließlich where ;${\displaystyle (i,j)}$${\displaystyle i=j}$
• Anfänglich ist die Länge des Pfads null;${\displaystyle (i,i)}$
• Ein Pfad kann dies nur verbessern, wenn er eine Länge kleiner Null hat, dh einen negativen Zyklus bezeichnet;${\displaystyle [i,k,\ldots,i]}$
• Somit ist nach dem Algorithmus negativ, wenn ein Pfad negativer Länge von zurück nach existiert .${\displaystyle (i,i)}$${\displaystyle i}$${\displaystyle i}$

Um negative Zyklen mit dem Floyd-Warshall-Algorithmus zu erkennen, kann man daher die Diagonale der Pfadmatrix untersuchen, und das Vorhandensein einer negativen Zahl zeigt an, dass der Graph mindestens einen negativen Zyklus enthält. Bei der Ausführung des Algorithmus können bei einem negativen Zyklus exponentiell große Zahlen auftreten, bis zu , wobei der größte Absolutwert einer negativen Flanke im Graphen ist. Um Überlauf-/Unterlaufprobleme zu vermeiden, sollte innerhalb der inneren for-Schleife des Algorithmus auf negative Zahlen auf der Diagonale der Pfadmatrix geprüft werden. Offensichtlich erzeugt in einem ungerichteten Graphen eine negative Kante einen negativen Kreis (dh einen geschlossenen Weg), der seine einfallenden Scheitelpunkte einbezieht. Betrachtet man alle Kanten des obigen Beispielgraphen als ungerichtet, so ist zB die Knotenfolge 4 – 2 – 4 ein Kreis mit der Gewichtssumme −2. ${\displaystyle \Omega (\cdot 6^{n-1}w_{max})}$${\displaystyle w_{max}}$

Wegrekonstruktion

Der Floyd-Warshall-Algorithmus liefert typischerweise nur die Längen der Pfade zwischen allen Scheitelpunktpaaren. Mit einfachen Modifikationen ist es möglich, eine Methode zu erstellen, um den tatsächlichen Pfad zwischen zwei beliebigen Endpunkt-Scheitelpunkten zu rekonstruieren. Obwohl man geneigt sein mag, den tatsächlichen Weg von jedem Scheitelpunkt zu jedem anderen Scheitelpunkt zu speichern, ist dies nicht notwendig und tatsächlich sehr speicheraufwendig. Stattdessen kann der kürzeste Pfadbaum für jeden Knoten in der Zeit berechnet werden, indem Speicher verwendet wird, um jeden Baum zu speichern, was es uns ermöglicht, einen Pfad aus zwei beliebigen verbundenen Knoten effizient zu rekonstruieren. ${\displaystyle \Theta (|E|)}$${\displaystyle \Theta (|V|)}$

Pseudocode

let dist be a ${\displaystyle |V|\times |V|}$ array of minimum distances initialized to ${\displaystyle \infty }$ (infinity)
let next be a ${\displaystyle |V|\times |V|}$ array of vertex indices initialized to null

procedure FloydWarshallWithPathReconstruction() is
    for each edge (u, v) do
        dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
        next[u][v] ← v
    for each vertex v do
        dist[v][v] ← 0
        next[v][v] ← v
    for k from 1 to |V| do // standard Floyd-Warshall implementation
        for i from 1 to |V|
            for j from 1 to |V|
                if dist[i][j] > dist[i][k] + dist[k][j] then
                    dist[i][j] ← dist[i][k] + dist[k][j]
                    next[i][j] ← next[i][k]

procedure Path(u, v)
    if next[u][v] = null then
        return []
    path = [u]
    while u ≠ v
        u ← next[u][v]
        path.append(u)
    return path

Analyse

Lassen Sie sein , die Anzahl der Ecken. Um alle von (für alle und ) aus denen von zu finden, sind Operationen erforderlich . Da wir mit der Folge von Matrizen , , , beginnen und diese berechnen , ist die Gesamtzahl der verwendeten Operationen . Daher ist die Komplexität des Algorithmus . ${\displaystyle n}$${\displaystyle |V|}$${\displaystyle n^{2}}$${\displaystyle \mathrm {shortestPath} (i,j,k)}$${\displaystyle i}$${\displaystyle j}$${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$${\displaystyle 2n^{2}}$${\displaystyle \mathrm {shortestPath} (i,j,0)=\mathrm {edgeCost} (i,j)}$${\displaystyle n}$${\displaystyle \mathrm {shortestPath} (i,j,1)}$${\displaystyle \mathrm {shortestPath} (i,j,2)}$${\displaystyle \ldots}$${\displaystyle \mathrm {shortestPath} (i,j,n)}$${\displaystyle n\cdot 2n^{2}=2n^{3}}$${\displaystyle \Theta (n^{3})}$

Anwendungen und Verallgemeinerungen

Mit dem Floyd-Warshall-Algorithmus können unter anderem folgende Probleme gelöst werden:

• Kürzeste Pfade in gerichteten Graphen (Floyd-Algorithmus).
• Transitive Schließung gerichteter Graphen (Warshall-Algorithmus). In Warshalls ursprünglicher Formulierung des Algorithmus ist der Graph ungewichtet und wird durch eine Boolesche Adjazenzmatrix dargestellt . Dann wird die Additionsoperation durch eine logische Verknüpfung (UND) und die minimale Operation durch eine logische Disjunktion (OR) ersetzt.
• Finden eines regulären Ausdrucks , der die reguläre Sprache bezeichnet, die von einem endlichen Automaten akzeptiert wird ( Kleene-Algorithmus , eine eng verwandte Verallgemeinerung des Floyd-Warshall-Algorithmus)
• Inversion von realen Matrizen ( Gauß-Jordan - Algorithmus )
• Optimale Streckenführung. In dieser Anwendung ist man daran interessiert, den Pfad mit dem maximalen Fluss zwischen zwei Scheitelpunkten zu finden. Dies bedeutet, dass anstelle von Minima wie im obigen Pseudocode, stattdessen Maxima verwendet werden. Die Kantengewichte stellen feste Beschränkungen für den Fluss dar. Pfadgewichtungen stellen Engpässe dar; so wird die obige Additionsoperation durch die minimale Operation ersetzt.
• Schnelle Berechnung von Pathfinder-Netzwerken .
• Breiteste Pfade/Maximale Bandbreitenpfade
• Berechnung der kanonischen Form von differenzgebundenen Matrizen (DBMs)
• Berechnung der Ähnlichkeit zwischen Graphen
• Transitive Schließung in UND/ODER/Schwellenwert-Graphen.

Implementierungen

Implementierungen sind für viele Programmiersprachen verfügbar .

• Für C++ in der boost::graph Bibliothek
• Für C# bei QuickGraph
• Für C# bei QuickGraphPCL (Eine Abzweigung von QuickGraph mit besserer Kompatibilität mit Projekten, die tragbare Klassenbibliotheken verwenden.)
• Für Java in der Apache Commons Graph- Bibliothek
• Für JavaScript in der Cytoscape- Bibliothek
• Für MATLAB im Paket Matlab_bgl
• Für Perl im Graph- Modul
• Für Python in der SciPy- Bibliothek (Modul scipy.sparse.csgraph ) oder der NetworkX- Bibliothek
• Für R , in Paketen e1071 und Rfast

Vergleich mit anderen Shortest-Path-Algorithmen

Der Floyd-Warshall-Algorithmus ist eine gute Wahl zum Berechnen von Pfaden zwischen allen Knotenpaaren in dichten Graphen , in denen die meisten oder alle Knotenpaare durch Kanten verbunden sind. Für dünn besetzte Graphen mit nicht-negativen Kantengewichten kann eine niedrigere asymptotische Komplexität erhalten werden, indem der Dijkstra-Algorithmus von jedem möglichen Startknoten ausgeführt wird, da die Laufzeit wiederholter Dijkstras (unter Verwendung von Fibonacci-Heaps ) im ungünstigsten Fall kleiner ist als die Laufzeit des Floyd –Warshall-Algorithmus when ist deutlich kleiner als . Für dünn besetzte Graphen mit negativen Kanten, aber keinen negativen Zyklen kann der Johnson-Algorithmus mit derselben asymptotischen Laufzeit wie der wiederholte Dijkstra-Ansatz verwendet werden. ${\displaystyle O(|E||V|+|V|^{2}\log |V|)}$${\displaystyle O(|V|^{3})}$${\displaystyle |E|}$${\displaystyle |V|^{2}}$

Es gibt auch bekannte Algorithmen, die eine schnelle Matrixmultiplikation verwenden , um die Berechnung des kürzesten Pfads aller Paare in dichten Graphen zu beschleunigen, aber diese machen typischerweise zusätzliche Annahmen bezüglich der Kantengewichte (wie z. B. dass sie kleine ganze Zahlen sein müssen). Außerdem würden sie wegen der hohen konstanten Faktoren in ihrer Laufzeit nur für sehr große Graphen eine Beschleunigung gegenüber dem Floyd-Warshall-Algorithmus bieten.

Verweise

Externe Links

• Interaktive Animation des Floyd-Warshall-Algorithmus
• Interaktive Animation des Floyd-Warshall-Algorithmus (TU München)