Algorithmus von Floyd und Warshall

Der Algorithmus von Floyd und Warshall (auch Floyd-Warshall-Algorithmus oder Tripel-Algorithmus), benannt nach Robert Floyd und Stephen Warshall, ist ein Algorithmus der Graphentheorie. In Floyds Version findet er die kürzesten Pfade zwischen allen Paaren von Knoten eines Graphen und berechnet deren Länge (APSP, all-pairs shortest path). In Warshalls Version findet er die transitive Hülle eines Graphen. Beide Versionen wurden 1962 vorgestellt und gehen auf einen Algorithmus zurück, den Stephen Kleene 1956 im Zusammenhang mit regulären Ausdrücken veröffentlicht hat.

Beschreibung

Der Floyd-Warshall-Algorithmus basiert auf dem Prinzip der dynamischen Programmierung.

Der Floyd-Algorithmus geht von folgender Beobachtung aus:

Geht der kürzeste Weg von $u$ nach $v$ durch $w$, dann sind die enthaltenen Teilpfade von $u$ nach $w$ und von $w$ nach $v$ schon minimal. Nimmt man also an, man kennt schon die kürzesten Wege zwischen allen Knotenpaaren, die nur über Knoten mit Index kleiner als $k$ führen, und man sucht alle kürzesten Wege über Knoten mit Index höchstens $k$, dann hat man für einen Pfad von $u$ nach $v$ zwei Möglichkeiten: Entweder er geht über den Knoten $k$, dann setzt er sich zusammen aus schon bekannten Pfaden von $u$ nach $k$ und von $k$ nach $v$, oder es ist der schon bekannte Weg von $u$ nach $v$ über Knoten mit Index kleiner als $k$.

Angenommen, der Graph ist gegeben durch seine Gewichtsmatrix $w$.

$w\left[i,j\right]$ ist das Gewicht der Kante von $i$ nach $j$, falls eine solche Kante existiert. Falls es keine Kante von $i$ nach $j$ gibt, ist $w\left[i,j\right]$ unendlich.

Dann kann man die Matrix $d$ der kürzesten Distanzen durch folgendes Verfahren bestimmen:

Algorithmus von Floyd

(1) Für alle $i,j:d\left[i,j\right]=w\left[i,j\right]$
(2) Für $k=1$ bis $n$
(3)   Für alle Paare $i,j$
(4)     $d\left[i,j\right]=\min(d\left[i,j\right],d\left[i,k\right]+d\left[k,j\right])$

Will man die transitive Hülle berechnen, ändert man den Algorithmus folgendermaßen ab:

$w$ ist die Adjazenzmatrix, das heißt, $w\left[i,j\right]$ ist 1, falls eine Kante von $i$ nach $j$ existiert, und 0, falls keine Kante existiert.

Die Matrix $d$ wird so definiert, dass $d[i,j]=1$, genau dann, wenn ein Pfad von $i$ nach $j$ existiert:

Algorithmus von Warshall

(1) Für $k=1$ bis $n$
(2)   Für $i=1$ bis $n$
(3)     Falls $d\left[i,k\right]=1$
(4)       Für $j=1$ bis $n$
(5)         Falls $d\left[k,j\right]=1$
(6)           $d\left[i,j\right]=1$

In Zeile (6) wird $d\left[i,j\right]$ auf 1 gesetzt, genau dann, wenn ein Pfad von $i$ nach $k$ und ein Pfad von $k$ nach $j$ über Kanten mit Index kleiner als $k$ existiert.

Der Floyd-Algorithmus funktioniert auch, wenn die Kanten negatives Gewicht haben. Zyklen mit negativer Länge werden (anders als beim Bellman-Ford-Algorithmus) jedoch nicht erkannt und führen zu einem falschen Ergebnis. Erkennbar sind negative Zyklen aber im Nachhinein durch negative Werte auf der Hauptdiagonalen der Distanzmatrix. Um numerische Probleme zu vermeiden, sollte man dies aber nicht erst im Nachhinein testen, sondern jedes Mal, wenn in Zeile (4) ein Diagonalelement geändert wird.

Zeitkomplexität

Die Laufzeit (Komplexität) des Floyd-Warshall-Algorithmus liegt in ${\mathcal {O}}(n^{3})$, weil für die drei Variablen $k$, $i$, $j$ die Werte von 1 bis $n$ durchlaufen werden müssen. Dabei ist $n$ Anzahl der Knoten des Graphen.

Vergleich mit anderen Algorithmen

Der Floyd-Warshall-Algorithmus ist eine gute Wahl für die Berechnung von Pfaden zwischen allen Knotenpaaren in dichten Graphen, in denen die meisten oder alle Knotenpaare mit Kanten verbunden sind. Für dünne Graphen mit nicht-negativen Kantengewichten ist es besser, den Dijkstra-Algorithmus von jedem möglichen Startknoten aus zu verwenden, weil die Laufzeit von wiederholtem Dijkstra $O(|E||V|+|V|^{2}\log |V|)$ unter Verwendung von Fibonacci-Heaps besser ist als die Laufzeit $O(|V|^{3})$ des Floyd-Warshall-Algorithmus, wenn $|E|$ signifikant kleiner als $|V|^{2}$ ist. Für dünne Graphen mit negativen Kanten, aber ohne negative Zyklen kann der Algorithmus von Johnson mit derselben asymptotischen Laufzeit wie der wiederholte Dijkstra-Ansatz verwendet werden.

Es sind auch Algorithmen bekannt, die eine schnelle Matrixmultiplikation verwenden, um die Berechnung des kürzesten Pfades zwischen allen Knotenpaaren in dichten Graphen zu beschleunigen, aber diese machen typischerweise zusätzliche Annahmen über die Kantengewichte, z. B. erfordern sie kleine ganze Zahlen. Aufgrund der hohen konstanten Faktoren in ihrer Laufzeit würden sie außerdem nur bei sehr großen Graphen eine Beschleunigung gegenüber dem Floyd-Warshall-Algorithmus bewirken.

Programmierung

Das folgende Beispiel in der Programmiersprache C# zeigt eine Implementierung des Floyd-Warshall-Algorithmus. eines gerichteten Graphen. Bei der Ausführung des Programms wird die Methode Main verwendet, die die kürzesten Abstände zwischen allen Paaren von Knoten auf der Konsole ausgibt. Die Matrix für die Abstände wird in einem zweidimensionalen Array vom Datentyp Integer gespeichert. Bei nicht verbundenen Knoten wird der Wert unendlich ausgegeben.

using System;

public class Program
{
	// Diese Methode gibt die kürzesten Abstände zwischen allen Paaren von Knoten zurück.
    static int[,] FloydWarshall(int[,] adjacencyMatrix, int numberOfNodes)
    {
        int[,] distances = new int[numberOfNodes, numberOfNodes]; // Deklariert die Matrix für die kürzesten Abstände als zweidimensionales Array vom Typ int
        // Initialisiert die Matrix für die kürzesten Abstände mit den Eingabewerten
        for (int i = 0; i < numberOfNodes; i++)
        {
            for (int j = 0; j < numberOfNodes; j++)
            {
                distances[i, j] = adjacencyMatrix[i, j];
            }
        }
        // Aktualisiert die Abstände zwischen allen Paaren von Knoten
        for (int k = 0; k < numberOfNodes; k++) // for-Schleife, die alle Knoten durchläuft, über die der Pfad zwischen den Knoten mit den Indexen i und j verläuft
        {
        	// Diese beiden for-Schleifen durchlaufen alle Paare von Knoten
            for (int i = 0; i < numberOfNodes; i++)
            {
                for (int j = 0; j < numberOfNodes; j++)
                {
                    if (distances[i, k] + distances[k, j] < distances[i, j]) // Wenn der Knoten mit dem Index k auf dem kürzesten Pfad zwischen den Knoten mit den Indexen i und j liegt
                    {
                        distances[i, j] = distances[i, k] + distances[k, j]; // Aktualisiert den Abstand zwischen den Knoten mit den Indexen i und j
                    }
                }
            }
        }
		return distances; // Gibt das zweidimensionale Array mit den kürzesten Abstände zurück
    }
    
	// Hauptmethode, die das Programm ausführt
    public static void Main(string[] args)
    {
        int numberOfNodes = 4;
        int threshold = int.MaxValue / numberOfNodes; // Schwellenwert für nicht verbundene Knoten
        int[,] distanceMatrix = { {0, 5, threshold, 10},
        	{threshold, 0, 3, threshold},
        	{threshold, threshold, 0, 1},
        	{threshold, threshold, threshold, 0} }; // Deklariert und initialisiert die Matrix mit den Abständen zwischen allen Punkten als zweidimensionales Array vom Typ int
        int[,] distances = FloydWarshall(distanceMatrix, numberOfNodes); // Aufruf der Methode
        
        // Gibt die Matrix mit den kürzesten Abständen auf der Konsole aus
        Console.WriteLine("Matrix mit den kürzesten Abständen zwischen allen Punkten");
        for (int i = 0; i < numberOfNodes; i++)
        {
        	for (int j = 0; j < numberOfNodes; j++)
            {
                if (distances[i, j] >= threshold) // Wenn der Schwellenwert überschritten ist, wird "INF" (unendlich) ausgegeben
                {
                    Console.Write("INF" + "\t"); // Ausgabe auf der Konsole
                }
                else
                {
                    Console.Write(distances[i, j] + "\t"); // Ausgabe auf der Konsole
                }
            }
            Console.WriteLine(); // Neue Zeile
        }
		
		Console.ReadLine();
    }
}

Beispiel

Der Algorithmus wird auf dem Graphen links unten mit vier Knoten ausgeführt:

Vor dem ersten Durchlauf der äußeren Schleife, oben mit k = 0 bezeichnet, entsprechen die einzigen bekannten Pfade den einzelnen Kanten im Diagramm. Bei k = 1 werden Pfade gefunden, die durch den Knoten 1 verlaufen: Insbesondere wird der Pfad [2,1,3] gefunden, der den Pfad [2,3] ersetzt, der weniger Kanten hat, aber länger ist. Bei k = 0 ist d[2, 3] = 3 und bei k = 1 wird dieser Wert mit d[2, 3] = d[2, 1] + d[1, 3] = 4 + (-2) = 2 überschrieben. Bei k = 2 werden Pfade gefunden, die durch die Knoten {1,2} verlaufen. 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 mit dem Schnittpunkt 2 angetroffen wurden. Der Pfad [4,2,3] wird nicht berücksichtigt, da [2,1,3] der kürzeste Pfad ist, der bisher von 2 bis 3 angetroffen wurde. Bei k = 3 werden alle Pfade gefunden, die durch die Knoten {1,2,3} verlaufen. Schließlich werden bei k = 4 alle kürzesten Pfade gefunden.

Die Distanzmatrix bei jeder Iteration von k mit den aktualisierten Abständen in Fettdruck lautet:

k = 0		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	3	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0

k = 1		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0

k = 2		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	3	−1	1	0

k = 3		j
		1	2	3	4
i	1	0	∞	−2	0
	2	4	0	2	4
	3	∞	∞	0	2
	4	3	−1	1	0

k = 4		j
		1	2	3	4
i	1	0	−1	−2	0
	2	4	0	2	4
	3	5	1	0	2
	4	3	−1	1	0

Andere Verfahren zur Berechnung kürzester Pfade

• Min-Plus-Matrixmultiplikations-Algorithmus
• A*-Algorithmus
• Algorithmus von Dijkstra
• Bellman-Ford-Algorithmus

Literatur

• Robert W. Floyd: Algorithm 97 (SHORTEST PATH). In: Communications of the ACM 5, 1962, 6, S. 345.
• Stephen Warshall: A Theorem on Boolean Matrices. In: Journal of the ACM 9, 1962, 1, ISSN 0004-5411, S. 11–12.

Weblinks

• Erklärung des Algorithmus mit Beispiel und Literaturhinweisen
• Java-Applet zur Demonstration
• Robert W. Floyd: Algorithm 97 (SHORTEST PATH), in Communications of the ACM, 5(6), p. 345, 1962.