Floyd-Warshall-Algorithmus (mit Java-Beispiel)

In dieser Serie über Pathfinding-Algorithmen hast du bereits Dijkstras Algorithmus, den A*-Algorithmus und den Bellman-Ford-Algorithmus kennengelernt. In diesem letzten Teil erfährst du, wie der Floyd-Warshall-Algorithmus funktioniert und für welche Zwecke man ihn einsetzt.

Um folgende Themen geht es im einzelnen:

• Was ist der Einsatzzweck des Floyd-Warshall-Algorithmus?
• Wie unterscheidet sich der Floyd-Warshall-Algorithmus von den bisher vorgestellten Pathfinding-Algorithmen?
• Wie funktioniert der Floyd-Warshall-Algorithmus (Schritt für Schritt an einem Beispiel erklärt)?
• Wie implementiert man den Floyd-Warshall-Algorithmus in Java?
• Wie bestimmt man die Zeitkomplexität des Floyd-Warshall-Algorithmus?

Den Quellcode der gesamten Artikelserie über Pathfinding-Algorithmen findest du in diesem GitHub-Repository.

Wann setzt man den Floyd-Warshall-Algorithmus ein?

Alle bisher vorgestellten Pathfinding-Algorithmen finden den kürzesten Weg von einem Ausgangsknoten zu einem Zielknoten (oder zu allen anderen Knoten eines Graphen).

Dijkstra priorisiert die Suche dabei nach Gesamtkosten vom Ausgangsknoten. A* priorisiert zusätzlich nach geschätzen Kosten bis zum Ziel. Und Bellman-Ford priorisiert gar nicht, kann dafür mit negativen Kantengewichten umgehen.

Floyd-Warshall hingegen findet die kürzesten Wege zwischen allen Paaren von Start- und Zielknoten (Floyds Variante).

Transitive Hülle eines Graphen

Alternativ berechnet Floyd-Warshall die sogenannte "transitive Hülle" eines Graphen (Warshalls Variante). Die transitive Hülle erweitert einen Graphen um Kanten zwischen allen indirekt verbundenen Knotenpaaren. Wenn der Graph beispielsweise zwei Kanten hat – eine von A nach B und eine von B nach C – dann vervollständigt die transitive Hülle den Graphen um die Kante von A nach C (da ein Weg von A nach C über B existiert).

Die folgende Grafik zeigt ein etwas komplexeres Beispiel mit vier Knoten – links der Ausgangsgraph und rechts dessen transitive Hülle. Die blauen Pfeile stellen die hinzugekommenen, indirekten Verbindungen dar:

Beide Aufgabenstellungen sind sehr ähnlich: Wenn ein kürzester Weg zwischen zwei Knotenpaaren existiert, dann gehört dieses Knotenpaar auch in die transitive Hülle – und vice versa. Daher werden die Varianten von Floyd und Warshall zu einem Algorithmus zusammengefasst.

Wie funktioniert der Floyd-Warshall-Algorithmus?

Der Algorithmus ist sehr einfach zu implementieren, wie du später feststellen wirst. Die Erklärung ist allerdings etwas knifflig. Ich werde den Algorithmus daher zuerst an einem Beispiel beschreiben.

Floyd-Warshall-Algorithmus – Beispiel

Der folgende Beispiel-Graph enthält fünf Knoten, bezeichnet mit A, B, C, D, E, und verschiedene gerichtete und gewichtete Kanten:

Die Zahlen an den Kanten (die Kantengewichte) stellen die Kosten für den jeweiligen Weg dar. Die Kosten von E nach B betragen beispielsweise 4.

Vorbereitung – Matrix aller Knotenpaare

Als Vorbereitung erstellen wir eine n × n große Matrix (n ist die Anzahl der Knoten), in der wir für jedes Knotenpaar (i, j) das Gewicht der Kante von i nach j eintragen, falls diese existiert. Ansonsten tragen wir unendlich (∞) ein. Auf der Diagonalen (die Entfernung eines Knoten zu sich selbst) tragen wir jeweils 0 ein.

Aus der Tabelle können wir beispielsweise ablesen: Die Kosten von A nach B betragen 2 (Zeile A, Spalte B).

Floyd-Warshall-Algorithmus – Schritt für Schritt

Wir führen nun die folgenden fünf Iterationen aus. Dabei betrachten wir jeweils einen der Knoten als möglichen Zwischenknoten.

Iteration 1 – Indirekte Wege über Zwischenknoten A

Wir vergleichen für alle Knotenpaare (i, j) die eingetragenen Kosten des direkten Weges mit den Kosten des indirekten Weges von i nach j über Knoten A – also die Kosten von Knoten i nach Knoten A plus der Kosten von Knoten A nach Knoten j (sofern solch ein Weg existiert). Sind die Kosten über Zwischenknoten A geringer als die bisherigen, ersetzen wir die Kosten in der Matrix.

Knotenpaare, bei denen i = j ist oder i = A oder j = A können wir überspringen. Die Entfernung eines Knotens zu sich selbst ist immer 0. Und wenn Start oder Ziel bereits A sind, gibt es nicht auch noch einen indirekten Weg über A.

Wir beginnen somit mit dem Knotenpaar (B, C). Die Kosten des direkten Weges sind 6 (abzulesen in Zeile B, Spalte C). Von B nach A ist aktuell kein Weg bekannt (in Zeile B, Spalte A steht unendlich). Wir können also in diesem Schritt keinen kürzeren Weg über A finden. Dementsprechend können wir auch keine kürzeren Wege für (B, D) und (B, E) via A finden.

Auch von C und D gibt es aktuell keine bekannten Wege zu Knoten A (Zeilen C und D, jeweils Spalte A enthält unendlich). Wir können somit für (C, B), (C, D), (C, E), (D, B), (D, C), (D, E) aktuell keine kürzeren Wege finden.

Beim Knotenpaar (E, B) beginnt es interessant zu werden. Die aktuellen Kosten des direkten Weges E→B betragen 4. Gibt es einen kürzeren Weg über Knoten A? Hier noch mal der entsprechende Ausschnitt des Graphen:

Die Kosten von E nach A betragen 1 (in der Tabelle Zeile E, Spalte A); die Kosten von A nach B betragen 2 (Zeile A, Spalte B). In Summe ergibt das 3. Die Kosten des indirekten Weges von E nach B über Knoten A sind also geringer als die des direkten Weges. Wir haben also folgenden, kürzeren Weg gefunden:

Wir ersetzen daher in Zeile E, Spalte B die 4 durch eine 3 (in der Tabelle fett hervorgehoben):

Wir betrachten als nächsten Knotenpaar (E, C). Die aktuellen Kosten betragen unendlich, da noch kein Weg gefunden wurde. Gibt es einen indirekten Weg über A, also E→A→C? Da aktuell kein Weg von A nach C bekannt ist (Zeile A, Spalte C enthält unendlich), ist die Antwort "nein".

Zuletzt schauen wir auf das Knotenpaar (E, D). Da auch von A nach D aktuell kein Weg bekannt ist, finden wir in diesem Schritt auch keinen indirekten Weg E→A→D.

Wir haben alle Knotenpaare betrachtet; Schritt 1 ist damit beendet. Wir kennen jetzt für alle Knotenpaare die niedrigsten Kosten, wenn wir auch indirekte Wege über Zwischenknoten A zulassen. Insbesondere haben wir in diesem Schritt einen kürzeren Weg von E nach B via Knoten A gefunden.

Iteration 2 – Indirekte Wege über Zwischenknoten B

In der zweiten Iteration vergleichen wir für alle Knotenpaare (i, j) wiederum die eingetragenen Kosten (dies sind nun entweder die Kosten des direkten Weges oder die über Zwischenknoten A – je nachdem welche geringer sind) mit den Kosten von i nach j über Knoten B.

Die Kosten zu und von Knoten B lesen wir aus der Matrix ab. Das heißt, dass dies nicht unbedingt die Kosten des direkten Weges zu/von Knoten B sein müssen. Es könnten auch die in Schritt 1 bestimmten, niedrigeren Kosten via Zwischenknoten A sein (z. B. von E nach B: 3 via A anstatt 4 direkt).

Wir beginnen mit Knotenpaar (A, C). Bisher wurde noch kein Weg gefunden (Zeile A, Spalte C enthält unendlich). Schauen wir uns den indirekten Weg über B an:

Die Kosten von A nach B betragen 2, und die Kosten von B nach C betragen 6. Die Summe ist 8. Das ist auf jeden Fall besser als gar kein Weg. Wir tragen daher in Zeile A, Spalte C die 8 ein:

Weiter geht es mit Knotenpaar (A, D). Auch hier ist bisher kein Weg bekannt. Gibt es einen Weg über Zwischenknoten B? Die Kosten von A nach B hatten wir eben bereits als 2 abgelesen. Von B nach D allerdings ist bisher kein Weg bekannt. Somit können wir auch keine Kosten für den Weg A→B→D bestimmen, und der Eintrag für Knotenpaar (A, D) bleibt unverändert (unendlich).

Genauso ergeht es uns mit Knotenpaar (A, E): Es gibt zwar nach wie vor den Weg A→B, aber keinen Weg B→E, somit auch keinen Weg A→B→E und damit keinen neuen Eintrag für Knotenpaar (A, E).

Wir kommen zu den Knotenpaaren (C, A), (C, D) und (C, E): Aktuell ist für alle drei Paare kein Weg bekannt. Es gibt einen Weg C→B mit Kosten von 7, aber von Zwischenknoten B weder einen Weg zu A, zu D oder zu E, somit also auch keine Wege C→B→A, C→B→D oder C→B→E. Die Einträge für die drei Knotenpaare bleiben daher unverändert (unendlich).

Knotenpaare (D, A), (D, C) und (D, E): Da es keinen Weg von Knoten D zu Zwischenknoten B gibt, können wir auch für diese drei Knotenpaare keine (oder keine kürzeren) Wege finden.

Knotenpaar (E, A): Es gibt zwar einen Weg von E nach B, aber keinen Weg von B nach A, somit auch keinen Weg E→B→A.

Bei Knotenpaar (E, C) kommt wieder etwas Schwung rein: Aktuell ist kein Weg bekannt. Gibt es einen Weg über B? Es gibt einen Weg E→B mit Kosten von 3 und einen Weg B→C mit Kosten von 6. Somit existiert ein Weg von E über B nach C mit Gesamtkosten von 9. Wir tragen die 9 in Zeile E, Spalte C ein:

Beachte, dass dies nicht heißt, dass der Weg von E nach C nur über Knoten B gehen muss. Denn der Weg von E nach B mit den Kosten 3 geht auch noch über den Knoten A (diesen hatten wir in Schritt 1 gefunden). Genau genommen haben wir jetzt also den Weg E→A→B→C gefunden:

Betrachten wir das letzte Knotenpaar in dieser Iteration, (E, D). Existiert ein Weg über Zwischenknoten B? Es existiert zwar ein Weg E→B mit Kosten 3, allerdings kein Weg B→D, somit also auch kein Weg E→B→D.

Die zweite Iteration ist beendet. Wir kennen nun für alle Knotenpaare die niedrigsten Kosten, wenn wir auch indirekte Wege über Knoten B – und damit auch indirekt über Knoten A – zulassen.

Iteration 3 – Indirekte Wege über Zwischenknoten C

Wir wiederholen das ganze: Jetzt vergleichen wir für alle Knotenpaare die eingetragenen Kosten mit denen über Zwischenknoten C. Die Kosten zu/von Knoten C, die wir wiederum aus der Matrix ablesen, können die des direkten Weges zu/von Knoten C sein, aber auch die in den vorherigen Iterationen bestimmten Kosten von indirekten Wegen via Knoten A und/oder B.

Wir beginnen mit Knotenpaar (A, B). Die Kosten von A nach Zwischenknoten C betragen 8 (diesen Weg hatten wir am Anfang der zweiten Iteration via B gefunden). Die Kosten von C nach B betragen 7. Der Weg über Zwischenknoten C hat also Gesamtkosten von 8 + 7 = 15. Dieser Weg ist deutlich länger als der aktuell hinterlegte mit Kosten von 2. Das ist in der Grafik auch gut zu erkennen: Der Weg A→B ist natürlich deutlich kürzer als A→B→C→B. Wir belassen den Eintrag für (A, B) also auf 2.

Knotenpaare (A, D) und (A, E): Die Kosten für A→C haben wir gerade abgelesen, es existieren allerdings keine Wege C→D bzw. C→E, somit also auch keine von A via C nach D bzw. von A via C nach E.

Knotenpaar (B, A), (B, D), (B, E): Die Kosten von B nach C betragen 6, von C existiert allerdings weder ein Pfad zu A, zu D oder zu E. Somit finden wir in dieser Iteration auch keinen der Wege B→C→A, B→C→D und B→C→E.

Knotenpaar (D, A): Es existiert ein Pfad von D nach C, allerdings keiner von C nach A, somit auch keiner von D via C nach A.

Für Knotenpaar (D, B) ist aktuell als Kosten unendlich hinterlegt, d. h. es ist noch kein Pfad bekannt. Das ändert sich jetzt: Es existiert der Pfad D→C mit Kosten 1 und der Pfad C→B mit Kosten 7. In Summe ergibt das 8:

Wir tragen somit in Zeile D, Spalte B die 8 ein:

Knotenpaar (D, E): Es ist kein Weg von Zwischenknoten C nach E bekannt, somit finden wir in dieser Iteration auch keinen Weg von D via C nach E.

Knotenpaare (E, A) und (E, D): Da keine Wege von Zwischenknoten C nach A bzw. nach D existieren, finden wir aktuell auch keinen Weg von E via C nach A bzw. von E via C nach D.

Knotenpaar (E, B): Die Kosten für den Weg E→C betragen 9, die Kosten für C→B betragen 7. In Summe also 16. Für den Weg E→B sind bereits Kosten von 3 hinterlegt. 16 ist deutlich schlechter, wir lassen also die 3 unverändert stehen.

Am Ende von Iteration 3 angekommen kennen wir die niedrigsten Kosten für alle Knotenpaare, wenn wir auch indirekte Wege über Knoten C – und damit auch über A und B – zulassen.

Iteration 4 – Indirekte Wege über Zwischenknoten D

Iteration 4 können wir abkürzen: Von keinem der Knoten gibt es einen Weg zu Zwischenknoten D. Somit werden wir für kein Knotenpaar einen Weg via D finden.

Iteration 5 – Indirekte Wege über Zwischenknoten E

In der letzten Iteration prüfen wir für alle Knotenpaare, ob wir einen kürzeren Weg über Zwischenknoten E finden.

Die Knotenpaare mit Startknoten A, B und C können wir schnell abhandeln: Von keinem dieser Knoten existiert ein Weg zu Zwischenknoten E, somit werden wir für keines dieser Knotenpaare einen Weg via E finden.

Knotenpaar (D, A): Die Kosten für den Pfad D→E betragen 3, die Kosten für E→A betragen 1. Es existiert also ein Weg von D via E nach A mit Gesamtkosten von 4:

Wir tragen die 4 in Zeile D, Spalte A ein:

Knotenpaar (D, B): Die Kosten für den Pfad D→E betragen weiterhin 3, die Kosten für E→B betragen ebenfalls 3. Ergibt in Summe 6. Wir haben also einen Weg von D via E nach B gefunden mit Gesamtkosten von 6. Aktuell sind hier Gesamtkosten von 8 eingetragen. Wir ersetzen die 8 durch 6:

Auch dieser Fall ist wieder ein Beispiel dafür, dass der Weg via Zwischenknoten E nicht der direkte Weg D→E→B ist, sondern tatsächlich D→E→A→B, da der kürzeste Weg von E nach B über A geht (den Weg E→A→B hatten wir in der ersten Iteration gefunden):

Das finale Knotenpaar ist (D, C): Die Kosten für den Pfad D→E betragen immer noch 3, die Kosten für E→C betragen 9. Ergibt in Summe 12. Dies ist schlechter als die für (D, C) aktuell hinterlegten Kosten von 1, die wir somit stehen lassen.

Wir haben das Ende der fünften Iteration erreicht und kennen nun die niedrigsten Kosten für alle Knotenpaare, wenn wir auch indirekte Wege über Knoten E (und damit auch über A, B, C, D) – also über beliebige anderen Knoten – zulassen.

Das Ziel des Algorithmus ist damit erreicht.

Erkennung negativer Zyklen im Graphen

Was ist ein negativer Zyklus? Und warum stellt dieser ein Problem dar? Diese Fragen habe ich im Artikel über den Bellman-Ford-Algorithmus beantwortet. Dieser Link führt direkt zu dem entsprechenden Abschnitt.

Ein negativer Zyklus von einem beliebigen Knoten aus führt dazu, dass die Kosten von diesem Knoten zu sich selbst negativ sind. Der Floyd-Warshall-Algorithmus macht es uns sehr leicht das zu erkennen. Die Kosten aller Knoten zu sich selbst lassen sich an der Matrix-Diagonalen direkt ablesen. Hier noch einmal die Matrix aus dem Beispiel von oben nach Durchlauf aller Iterationen:

In der Diagonalen (fett hervorgehoben) befinden sich ausschließlich Nullen. Das heißt: Es existiert kein negativer Zyklus.

Sollte sich in wenigstens einem Feld auf der Diagonalen eine negative Zahl befinden, wäre ein negativer Zyklus erkannt. Der Algorithmus würde dann mit einer Fehlermeldung terminieren.

Floyd-Warshall-Algorithmus – Bestimmung der kürzesten Pfade

In der oben beschriebenen Grundform berechnet der Floyd-Warshall-Algorithmus nur die Kosten der kürzesten Pfade zwischen zwei Knoten, nicht jedoch die Pfade selbst (d. h. über welche Zwischenknoten der kürzeste Pfad führt).

Man kann den Algorithmus jedoch relativ einfach erweitern, so dass die Bestimmung des kürzesten Pfades zwischen zwei Knoten leicht möglich ist.

Dazu benötigen wir eine zweite Matrix der Größe n × n, die sogenannte "Nachfolgermatrix". Hier tragen wir für jedes Knotenpaar (i, j) initial den jeweiligen Endknoten j ein. Das bedeutet, dass der Weg von i nach j initial über den Nachfolger j führt.

Sobald wir für ein beliebiges Paar (i, j) einen kürzeren Weg über Zwischenknoten k finden, tragen wir in der Matrix an Position (i, j) den aktuellen Wert der Matrix von Position (i, k) ein. Das bedeutet, dass der Weg von i nach j nun über denselben Nachfolger führt wie der Weg von i nach k. Der Nachfolger kann k selbst sein, aber auch ein weiterer Zwischenknoten auf dem kürzesten Weg zu k.

Im Beispiel oben würden wir die Nachfolgermatrix initial wie folgt befüllen:

In Iteration 1 finden wir von E nach B einen kürzeren Weg über A. Der Nachfolger von E auf dem Weg zu A (Zeile E, Spalte A) ist A; somit tragen wir A auch als Nachfolger von E auf dem Weg nach B (Zeile E, Spalte B) ein:

Versuche gerne einmal selbst (als Übung) die Matrix über alle fünf Iterationen zu aktualisieren.

Am Ende sollte sie wie folgt aussehen (alle Änderungen sind fett markiert):

Wie können wir daraus kürzeste Wege ablesen?

Nehmen wir den Weg von D nach B, den wir in der fünften Iteration berechnet hatten.

Wir lesen Schritt für Schritt aus der Matrix ab:

• Zeile D, Spalte B: Der direkte Nachfolger von D auf dem Weg zu B ist: E
• Zeile E, Spalte B: Der direkte Nachfolger von E auf dem Weg zu B ist: A
• Zeile A, Spalte B: Der direkte Nachfolger von A auf dem Weg zu B ist: B (Zielknoten erreicht)

Der vollständige kürzeste Weg lautet also D→E→A→B.

Hier noch einmal zum Vergleich die Grafik aus der fünften Iteration:

Der aus der Nachfolgermatrix abgelesene Pfad stimmt mit dem eingezeichneten Pfad überein.

Floyd-Warshall-Algorithmus – Informelle Beschreibung

Die informelle Beschreibung – und auch der Code (dieser folgt im nächsten Kapitel) – sind überraschend einfach. Die Schritte für das Bestimmen der vollständigen Wege sind als optional gekennzeichnet. Um die zwei Matrizen nicht zu verwechseln, bezeichne ich sie im Folgenden als Kostenmatrix und Nachfolgermatrix.

Vorbereitung:

1. Erstelle die Kostenmatrix der Größe n × n (n ist die Anzahl der Knoten).
2. Trage für jedes Knotenpaar (i, j) die Kosten des direkten Pfades von i nach j ein, falls dieser existiert; trage ansonsten unendlich ein.
3. Trage auf der Diagonalen Nullen ein.

Optionale Vorbereitung: Erstellung der Nachfolgermatrix

1. Erstelle die Nachfolgermatrix der Größe n × n.
2. Trage für jedes Knotenpaar (i, j) den Wert j ein.

Führe folgende Iteration n mal aus; k sei dabei der Schleifenzähler und stehe für den Zwischenknoten:

• Für jedes Knotenpaar (i, j):
  • Berechne die Summe der Kosten des Weges i→k (abzulesen in Zeile i, Spalte k der Kostenmatrix) und der Kosten des Weges k→j (abzulesen in Zeile k, Spalte j der Kostenmatrix).
  • Ist die Summe kleiner als die Kosten des Weges i→j (abzulesen in Zeile i, Spalte j der Kostenmatrix), dann
    1. trage die neuen, niedrigeren Kosten in Zeile i, Spalte j der Kostenmatrix ein;
    2. (optional) kopiere in der Nachfolgermatrix den Wert aus Feld (i, k) ins Feld (i, j).

Prüfe abschließend, ob auf der Diagonalen der Kostenmatrix eine negative Zahl vorkommt. Wenn ja, beende den Algorithmus mit der Fehlermeldung "Negativer Zyklus erkannt". Ansonsten ist der Algorithmus erfolgreich durchgelaufen.

Floyd-Warshall-Algorithmus in Java

In diesem Kapitel zeige ich dir Schritt für Schritt, wie du den Floyd-Warshall-Algorithmus in Java implementierst. Du findest den vollständigen Quellcode im Paket eu.happycoders.pathfinding.floyd_warshall des GitHub-Repositories.

Datenstruktur für den Graph: Guava ValueGraph

Wie auch in den vorangegangenen Teilen der Serie verwenden wir den MutableValueGraph aus den Google Core Libraries for Java (Guava). Im folgenden Code-Ausschnitt siehst du, wie man den gerichteten Graphen aus dem Beispiel oben erstellt (Methode TestWithSampleGraph.createSampleGraph()):

private static ValueGraph<String, Integer> createSampleGraph() {
  MutableValueGraph<String, Integer> graph = ValueGraphBuilder.directed().build();
  graph.putEdgeValue("A", "B", 2);
  graph.putEdgeValue("B", "C", 6);
  graph.putEdgeValue("C", "B", 7);
  graph.putEdgeValue("D", "C", 1);
  graph.putEdgeValue("D", "E", 3);
  graph.putEdgeValue("E", "A", 1);
  graph.putEdgeValue("E", "B", 4);
  return graph;
}Code-Sprache: Java (java)

Die Typparameter von VaueGraph sind:

1. Typ der Knoten: wir verwenden hier String für die Knotennamen "A" bis "E".
2. Typ der Kantengewichte: für das Beispiel verwenden wir Integer.

In der putEdgeValue()-Methode wird zuerst der Startknoten angegeben, gefolgt vom Zielknoten und dem Kantengewicht.

Datenstruktur für die Kosten- und Nachfolgermatrix

Als Datenstruktur für die Matrizen bieten sich zweidimensionale Arrays an:

int n = graph.nodes().size();
int[][] costs = new int[n][n];
int[][] successors = new int[n][n];Code-Sprache: Java (java)

Da unser Algorithmus am Ende beide Matrizen zurückgeben soll, kapseln wir beide in der Klasse FloydWarshallMatrices. Im Repository siehst du, dass diese Klasse auch eine print()-Methode hat, mit der wir zum Test die Matrizen auf der Konsole ausgeben können.

Indizierung der Knoten im Graphen

Die Zeilen und Spalten der zweidimensionalen Arrays werden mit Index 0 bis n-1 adressiert. Unsere Knoten werden allerdings durch Namen identifiziert, nicht durch Zahlen. Wir benötigen also eine Abbildungsvorschrift zwischen Index und Knotenname.

Die Methode graph.nodes() liefert ein Set der Knoten, also eine nicht indizierbare Datenstruktur.

Wir können das Set jedoch sehr einfach in ein Array konvertieren:

String[] nodes = graph.nodes().toArray(new String[n]);Code-Sprache: Java (java)

Mittels nodes[i] können wir nun für die Zeile oder Spalte i den zugehörigen Knotennamen bestimmen.

Vorbereitung: Füllen der Matrizen

Die Matrizen füllen wir initial wie folgt (Methode FloydWarshall.findShortestPaths()). Die Variable m steht hier für die Instanz des FloydWarshallMatrices-Klasse, die die zwei Matrizen enthält.

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    Optional<Integer> edgeValue = graph.edgeValue(nodes[i], nodes[j]);
    m.costs[i][j] = i == j ? 0 : edgeValue.orElse(Integer.MAX_VALUE);
    m.successors[i][j] = edgeValue.isPresent() ? j : -1;
  }
}Code-Sprache: Java (java)

In der Kostenmatrix verwenden wir Integer.MAX_VALUE als Repräsentation für unendlich. Das funktioniert natürlich nur, solange wir mit den Kosten nicht in die Nähe dieses Wertes (2³¹-1) kommen. Für die Demonstration des Algorithmus ist es eine ausreichende Abstraktion.

In der Nachfolgermatrix tragen wir -1 ein, wenn es für ein Knotenpaar keinen Pfad gibt.

Wir könnten bei beiden Matrizen auch mit Integer-Objekten und null-Werten arbeiten oder gar mit Optional<Integer>, das wäre allerdings weniger performant.

Iterationen

Für die Iterationen verschalteln wir drei Schleifen ineinander:

• Die äußere, mit Schleifenzähler k, iteriert über die Zwischenknoten.
• Die zwei inneren, mit Schleifenzählern i und j, iterieren über alle Knotenpaare.

for (int k = 0; k < n; k++) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int costViaNodeK = addCosts(m.costs[i][k], m.costs[k][j]);
      if (costViaNodeK < m.costs[i][j]) {
        m.costs[i][j] = costViaNodeK;
        m.successors[i][j] = m.successors[i][k];
      }
    }
  }
}Code-Sprache: Java (java)

Innerhalb der Schleifen addieren wir die Kosten der Wege i→k und k→j und vergleichen die Summe mit den Kosten des Weges i→j. Ist die Summe über Zwischenknoten k kleiner, dann setzen wir die Kosten für den Weg i→j auf die neu berechneten, geringeren Kosten, und wir setzen als Nachfolgerknoten für den Weg i→j den Nachfolgerknoten des Weges i→k.

Die Methode addCosts() liefert unendlich (in Form von Integer.MAX_VALUE) zurück, wenn einer der beiden Summanden unendlich ist:

private static int addCosts(int a, int b) {
  if (a == Integer.MAX_VALUE || b == Integer.MAX_VALUE) {
    return Integer.MAX_VALUE;
  }
  return a + b;
}Code-Sprache: Java (java)

Erkennung von negativen Zyklen

Nach Durchlauf der Iterationen prüfen wir auf negative Zyklen:

for (int i = 0; i < n; i++) {
  if (m.costs[i][i] < 0) {
    throw new IllegalArgumentException("Graph has a negative cycle");
  }
}Code-Sprache: Java (java)

Am Ende liefert die findShortestPaths()-Methode die FloydWarshallMatrices-Instanz m zurück.

Bestimmung des kürzesten Pfades zwischen zwei Knoten

Die Berechnung des kürzesten Pfades von einem Knoten zu einem anderen habe ich in der Methode FloydWarshallMatrices.getPath() implementiert. i und j sind dabei die Indizes von Start- und Endknoten:

if (successors[i][j] == -1) {
  return Optional.empty();
}

List<String> path = new ArrayList<>();
path.add(nodes[i]);

while (i != j) {
  i = successors[i][j];
  path.add(nodes[i]);
}

return Optional.of(List.copyOf(path));Code-Sprache: Java (java)

Zuerst wird geprüft, ob successors[i][j] gleich -1 ist. Wenn das der Fall ist, existiert kein Pfad von i nach j, und die Methode gibt ein leeres Optional zurück.

Ansonsten wird eine Liste path angelegt und mit dem Ausgangsknoten und dann – nach und nach – mit den Folgeknoten des Weges befüllt. Schließlich wird eine nicht modifizierbare Kopie der Liste (Stichwort "defensive copy") zurückgeliefert.

Aufruf der findShortestPaths()-Methode

Folgende drei Beispiele im Repository zeigen den Aufruf der findShortestPaths()-Methode:

• TestWithSampleGraph: In diesem Test werden die kürzesten Pfade des Beispielgraphen aus diesem Artikel berechnet.
• TestWithSampleGraphFromBellmanFord: Dieser Test berechnet die kürzesten Pfade in dem Beispiel-Graphen aus dem Artikel über den Bellman-Ford-Algorithmus.
• TestWithNegativeCycle: Dieser Test ruft die findShortestPaths()-Methode für einen Beispiel-Graphen mit negativem Zyklus (ebenfalls aus dem Bellman-Ford-Artikel) auf.

Zeitkomplexität des Floyd-Warshall-Algorithmus

Die Zeitkomplexität des Floyd-Warshall-Algorithmus ist schnell bestimmt. Wir haben drei ineinander geschachtelte Schleifen, die jeweils n Durchläufe zählen. In der innersten Schleife haben wir einen Vergleich, der mit konstantem Aufwand durchführbar ist. Der Vergleich wird also n × n × n mal – oder n³ mal – ausgeführt.

Die Zeitkomplexität von Floyd-Warshall beträgt somit: O(n³)

Laufzeit des Floyd-Warshall-Algorithmus

Mit dem Programm TestFloydWarshallRuntime können wir prüfen, ob die Laufzeit des Algorithmus zur hergeleiteten Zeitkomplexität O(n³) passt. Das Programm erstellt zufällige Graphen verschiedener Größen und berechnet darin die kürzesten Pfade. Das Programm wiederholt jeden Test 50 mal und gibt den Median aller Messwerte aus.

Das folgende Diagramm zeigt die Laufzeit in Abhängigkeit von der Größe des Graphen:

Das kubische Wachstum ist gut zu erkennen: Bei Verdopplung der Anzahl der Knoten (z. B. von 1.000 auf 2.000) verachtfacht sich die benötigte Zeit (von 700 ms auf etwa 6 s).

Floyd-Warshall vs. Bellman-Ford vs. Dijkstra

Im folgenden Diagramm habe ich die Laufzeiten von Floyd-Warshall, Bellman-Ford (optimiert und nicht optimiert) und Dijkstra (mit Fibonacci Heap) gegenübergestellt:

Floyd-Warshall ist, wie aufgrund der Zeitkomplexität zu erwarten war, noch einmal langsamer als Bellman-Ford.

Wann sollte also welcher Algorithmus eingesetzt werden?

• Floyd-Warshall sollte nur dann eingesetzt werden, wenn die kürzesten Wege zwischen allen Knotenpaaren gesucht werden.
• Bellman-Ford sollte eingesetzt werden, wenn der Graph negative Kantengewichte enthält.
• A* sollte eingesetzt werden, wenn der Graph keine negativen Kantengewichte enthält und sich eine Heuristik definieren lässt.
• Ohne negative Kantengewichte und ohne Heuristik sollte Dijkstras Algorithmus eingesetzt werden.

Zusammenfassung

Dieser Artikel hat dir gezeigt, wann man den Floyd-Warshall-Algorithmus einsetzt (wenn man die kürzesten Entfernungen zwischen allen Knotenpaaren benötigt), wie er funktioniert und wie er negative Zyklen identifiziert.

Die Zeitkomplexität ist mit O(n³) deutlich schlechter als die aller bisher vorgestellten Pathfinding-Algorithmen. Floyd-Warshall sollte daher wirklich nur für den vorgesehenen Einsatzzweck verwendet werden.

Damit endet die Serie über Pathfinding-Algorithmen. Wenn dir der Artikel gefallen hat, teile ihn gerne über einen der Share-Buttons am Ende. Hast du Fragen oder Anregungen? Dann hinterlasse mir gerne einen Kommentar. Möchtest du informiert werden, wenn der nächste Artikel veröffentlicht wird? Dann trage dich gerne in den HappyCoders E-Mail-Verteiler ein.