Wikipedia

Algorithmus von Floyd und Warshall

Algorithmus der Graphentheorie
(Weitergeleitet von Warshall-Algorithmus)

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

Bearbeiten

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

Angenommen, der Graph ist gegeben durch seine Gewichtsmatrix  .

  ist das Gewicht der Kante von   nach  , falls eine solche Kante existiert. Falls es keine Kante von   nach   gibt, ist   unendlich.

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

Algorithmus von Floyd

(1) Für alle  
(2) Für   bis  
(3)   Für alle Paare  
(4)      

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

  ist die Adjazenzmatrix, das heißt,   ist 1, falls eine Kante von   nach   existiert, und 0, falls keine Kante existiert.

Die Matrix   wird so definiert, dass  , genau dann, wenn ein Pfad von   nach   existiert: 

Algorithmus von Warshall

(1) Für   bis  
(2)   Für   bis  
(3)     Falls  
(4)       Für   bis  
(5)         Falls  
(6)            

In Zeile (6) wird   auf 1 gesetzt, genau dann, wenn ein Pfad von   nach   und ein Pfad von   nach   über Kanten mit Index kleiner als   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.[1]

Zeitkomplexität

Bearbeiten

Die Laufzeit (Komplexität) des Floyd-Warshall-Algorithmus liegt in  , weil für die drei Variablen  ,  ,   die Werte von 1 bis   durchlaufen werden müssen. Dabei ist   Anzahl der Knoten des Graphen.

Vergleich mit anderen Algorithmen

Bearbeiten

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   unter Verwendung von Fibonacci-Heaps besser ist als die Laufzeit   des Floyd-Warshall-Algorithmus, wenn   (E. Edges, Kanten) signifikant kleiner als   ist (V. Vertices, Knoten). 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.[2]

Programmierung

Bearbeiten

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.[3]

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

Bearbeiten

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

Bearbeiten

Literatur

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  1. ↑ Stefan Hougardy: The Floyd–Warshall algorithm on graphs with negative cycles. In: Information Processing Letters. 110. Jahrgang, Nr. 8–9, April 2010, S. 279–281 (sciencedirect.com).
  2. ↑ Uri Zwick: All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication
  3. ↑ GeeksforGeeks: Floyd Warshall Algorithm
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Algorithmus_von_Floyd_und_Warshall&oldid=245119866“