imported>Wieggy: weitere Ergänzungen

2025-01-29T18:11:23Z

weitere Ergänzungen

Neue Seite

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ürzester Pfad|kürzesten Pfade]] zwischen allen Paaren von Knoten eines [[Graph (Graphentheorie)|Graphen]] und berechnet deren Länge (''APSP, all-pairs shortest path''). In Warshalls Version findet er die [[Transitive Hülle (Relation)|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ärer Ausdruck|regulären Ausdrücken]] veröffentlicht hat.

== Beschreibung ==
Der Floyd-Warshall-Algorithmus basiert auf dem Prinzip der [[dynamische Programmierung|dynamischen Programmierung]].

Der Floyd-Algorithmus geht von folgender Beobachtung aus:

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

Angenommen, der [[Graph (Graphentheorie)|Graph]] ist gegeben durch seine [[Adjazenzmatrix|Gewichtsmatrix]] <math>w</math>.

<math>w\left[i,j\right]</math> ist das Gewicht der Kante von <math>i</math> nach <math>j</math>, falls eine solche Kante existiert. Falls es keine [[Kante (Graphentheorie)|Kante]] von <math>i</math> nach <math>j</math> gibt, ist <math>w\left[i,j\right]</math> unendlich.

Dann kann man die [[Matrix (Mathematik)|Matrix]] <math>d</math> der kürzesten Distanzen durch folgendes Verfahren bestimmen:
'''Algorithmus von Floyd'''

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

Will man die [[transitive Hülle (Relation)|transitive Hülle]] berechnen, ändert man den Algorithmus folgendermaßen ab:

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

Die Matrix <math>d</math> wird so definiert, dass <math>d[i,j]= 1</math>, genau dann, wenn ein [[Weg (Graphentheorie)|Pfad]] von <math>i</math> nach <math>j</math> existiert:
'''Algorithmus von Warshall'''

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

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

Der Floyd-Algorithmus funktioniert auch, wenn die Kanten negatives Gewicht haben. [[Zyklus (Graphentheorie)|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 [[Hauptdiagonale]]n 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.<ref>
{{cite journal
| title = The Floyd–Warshall algorithm on graphs with negative cycles
| author = Stefan Hougardy
| journal = Information Processing Letters
| url = http://www.sciencedirect.com/science/article/pii/S002001901000027X
| volume = 110
| issue = 8–9
| date = 2010-04
| pages = 279–281
| language = en
| doi=10.1016/j.ipl.2010.02.001
}}</ref>

== Zeitkomplexität ==
Die Laufzeit ([[Komplexitätstheorie|Komplexität]]) des Floyd-Warshall-Algorithmus liegt in <math> \mathcal{O}(n^3) </math>, weil für die drei [[Variable (Programmierung)|Variablen]] <math>k</math>, <math>i</math>, <math>j</math> die Werte von 1 bis <math>n</math> durchlaufen werden müssen. Dabei ist <math>n</math> Anzahl der [[Knoten (Graphentheorie)|Knoten]] des [[Graph (Graphentheorie)|Graphen]].

== Vergleich mit anderen Algorithmen ==
Der Floyd-Warshall-Algorithmus ist eine gute Wahl für die Berechnung von [[Pfad (Graphentheorie)|Pfaden]] zwischen allen Knotenpaaren in dichten [[Graph (Graphentheorie)|Graphen]], in denen die meisten oder alle Knotenpaare mit [[Kante (Graphentheorie)|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 (Informatik)|Laufzeit]] von wiederholtem Dijkstra <math>O(|E||V|+|V|^2\log|V|)</math> unter Verwendung von [[Fibonacci-Heap|Fibonacci-Heaps]] besser ist als die Laufzeit <math>O(|V|^3)</math> des Floyd-Warshall-Algorithmus, wenn <math>|E|</math> (E. Edges, Kanten) signifikant kleiner als <math>|V|^2</math> ist (V. Vertices, Knoten). Für dünne Graphen mit negativen Kanten, aber ohne negative [[Zyklus (Graphentheorie)|Zyklen]] kann der [[Algorithmus von Johnson]] mit derselben [[Asymptotische Laufzeit|asymptotischen Laufzeit]] wie der wiederholte Dijkstra-Ansatz verwendet werden.

Es sind auch [[Algorithmus|Algorithmen]] bekannt, die eine schnelle [[Matrixmultiplikation]] verwenden, um die Berechnung des [[Kürzester Pfad|kürzesten Pfades]] zwischen allen Knotenpaaren in dichten [[Graph (Graphentheorie)|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 (Informatik)|Laufzeit]] würden sie außerdem nur bei sehr großen Graphen eine Beschleunigung gegenüber dem Floyd-Warshall-Algorithmus bewirken.<ref>{{Literatur |Autor=Uri Zwick |Titel=All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication |DOI=10.48550/arXiv.cs/0008011 |Datum=2024-04-26 |Sprache=en |Online=https://arxiv.org/pdf/cs/0008011.pdf |Format=PDF}}</ref>

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C-Sharp|C#]] zeigt eine Implementierung des Floyd-Warshall-Algorithmus. eines [[Gerichteter Graph|gerichteten Graphen]]. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''Main'' verwendet, die die kürzesten [[Abstand|Abstände]] zwischen allen Paaren von [[Knoten (Graphentheorie)|Knoten]] auf der Konsole ausgibt. Die [[Matrix (Mathematik)|Matrix]] für die Abstände wird in einem zweidimensionalen [[Feld (Datentyp)|Array]] vom [[Datentyp]] [[Integer (Datentyp)|Integer]] gespeichert. Bei nicht verbundenen Knoten wird der Wert [[Unendlichkeit|unendlich]] ausgegeben.<ref>{{Internetquelle |url=https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/ |titel=Floyd Warshall Algorithm |werk=geeksforgeeks |datum=2025-01-29 |abruf=2025-01-29 |sprache=en}}</ref><syntaxhighlight lang="c#">
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();
}
}
</syntaxhighlight>

== Beispiel ==
Der Algorithmus wird auf dem Graphen links unten mit vier [[Knoten (Graphentheorie)|Knoten]] ausgeführt:

[[Datei:Floyd-Warshall example.svg|rahmenlos|alternativtext=|600x600px]]

Vor dem ersten Durchlauf der äußeren Schleife, oben mit k = 0 bezeichnet, entsprechen die einzigen bekannten [[Pfad (Graphentheorie)|Pfade]] den einzelnen Kanten im [[Diagramm]]. Bei k = 1 werden Pfade gefunden, die durch den [[Knoten (Graphentheorie)|Knoten]] 1 verlaufen: Insbesondere wird der Pfad [2,1,3] gefunden, der den Pfad [2,3] ersetzt, der weniger [[Kante (Graphentheorie)|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:
{| class=wikitable style="float:left; margin:10px; text-align:center;"
|-
| colspan="2" rowspan="2" |k = 0
| colspan="4" |j
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |i
! 1
| 0 || ∞ || −2 || ∞
|-
! 2
| 4 || 0 || 3 || ∞
|-
! 3
| ∞ || ∞ || 0 || 2
|-
! 4
| ∞ || −1 || ∞ || 0
|}

{| class=wikitable style="float:left; margin:10px; text-align:center;"
|-
| colspan="2" rowspan="2" |k = 1
| colspan="4" |j
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |i
! 1
| 0 || ∞ || −2 || ∞
|-
! 2
| 4 || 0 || '''2''' || ∞
|-
! 3
| ∞ || ∞ || 0 || 2
|-
! 4
| ∞ || −1 || ∞ || 0
|}

{| class=wikitable style="float:left; margin:10px; text-align:center;"
|-
| colspan="2" rowspan="2" |k = 2
| colspan="4" |j
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |i
! 1
| 0 || ∞ || −2 || ∞
|-
! 2
| 4 || 0 || 2 || ∞
|-
! 3
| ∞ || ∞ || 0 || 2
|-
! 4
| '''3''' || −1 || '''1''' || 0
|}

{| class=wikitable style="float:left; margin:10px; text-align:center;"
|-
| colspan="2" rowspan="2" |k = 3
| colspan="4" |j
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |i
! 1
| 0 || ∞ || −2 || '''0'''
|-
! 2
| 4 || 0 || 2 ||'''4'''
|-
! 3
| ∞ || ∞ || 0 || 2
|-
! 4
| 3 || −1 || 1 || 0
|}

{| class=wikitable style="float:left; margin:10px; text-align:center;"
|-
| colspan="2" rowspan="2" |k = 4
| colspan="4" |j
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |i
! 1
| 0 || '''−1''' || −2 || 0
|-
! 2
| 4 || 0 || 2 || 4
|-
! 3
| '''5''' || '''1''' || 0 || 2
|-
! 4
| 3 || −1 || 1 || 0
|}
<div style="clear:both;"></div>

== Andere Verfahren zur Berechnung kürzester Pfade ==
* [[Min-Plus-Matrixmultiplikations-Algorithmus]]
* [[A*-Algorithmus]]
* [[Algorithmus von Dijkstra]]
* [[Bellman-Ford-Algorithmus]]

== Literatur ==
* {{Literatur |Autor=Robert W. Floyd |Titel=Algorithm 97 – SHORTEST PATH |DOI=10.1145/367766.368168 |Sammelwerk=Communications of the [[Association for Computing Machinery|ACM]] |Nummer=5 |Band=6 |Seiten=345 |Datum=1962 |Sprache=en}}
* {{Literatur |Autor=Stephen Warshall |Titel=A Theorem on Boolean Matrices |DOI=10.1145/321105.321107 |Sammelwerk=Communications of the ACM |Nummer=9 |Band=1 |Seiten=11-12 |Datum=1962 |Sprache=en |ISSN=0004-5411}}

== Weblinks ==
* {{Webarchiv |url=http://www.inf.fh-flensburg.de/lang/algorithmen/graph/warshall.htm |wayback=20190912193127 |text=Erklärung des Algorithmus mit Beispiel und Literaturhinweisen}}
* {{Internetquelle |url=http://www.pms.ifi.lmu.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html#visualization |titel=Java-Applet zur Demonstration |hrsg=Ludwig-Maximilians-Universität München |abruf=2025-01-29 |sprache=de}}

== Einzelnachweise ==
<references />

[[Kategorie:Dynamische Programmierung]]
[[Kategorie:Reise- und Routenplanung]]
[[Kategorie:Graphsuchalgorithmus|Floyd und Warshall]]

Algorithmus von Floyd und Warshall - Versionsgeschichte

imported>Wieggy: weitere Ergänzungen