Floyd Warshall Algorithm

MittelKürzeste Wege Dynamische Programmierung

+10

Ein gerichteter Graph mit n Knoten, nummeriert von 0 bis n-1, ist als n-mal-n-Matrix gegeben: matrix[i][j] ist das Gewicht der Kante von Knoten i zu Knoten j oder -1, wenn keine Kante vorhanden ist, und matrix[i][i] ist 0. Die Länge eines Pfads ist die Summe der Kantengewichte.

Gib eine n-mal-n-Matrix zurück, deren Eintrag [i][j] die Länge des kürzesten Pfads von Knoten i zu Knoten j ist oder -1, wenn Knoten j von Knoten i aus nicht erreichbar ist.

Funktion

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: die Kantengewichte: matrix[i][j] ist das Gewicht der Kante von i nach j oder -1, wenn keine vorhanden ist
Gibt zurückinteger-2d-array: die kürzeste Entfernung für jedes Knotenpaar, -1, wenn kein Pfad existiert

Einschränkungen

1 ≤ n ≤ 100, wobei n = matrix.length = matrix[i].length
matrix[i][i] = 0
Für i ≠ j ist matrix[i][j] -1 (keine Kante) oder 0 ≤ matrix[i][j] ≤ 1000.
Kanten verlaufen in eine Richtung: matrix[i][j] und matrix[j][i] sind unabhängig.

Beispiele

Eingabe: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
Ausgabe: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
Erklärung: Über Knoten 1 erreicht Knoten 0 Knoten 2 mit Kosten von 6 statt 11 und Knoten 3 mit Kosten von 9. Knoten 1 erreicht Knoten 0 über Knoten 2 mit Kosten von 3. Von Knoten 3 geht nichts ab, daher steht in seiner Zeile außerhalb der Diagonale -1.

Eingabe: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
Ausgabe: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
Erklärung: Die Kante von 2 nach 1 hat das Gewicht 0, daher kostet 0 → 2 → 1 1, weniger als die direkte Verbindung mit Gewicht 6. Von Knoten 1 geht keine Kante weg und in Knoten 0 führt keine Kante hinein, daher bleiben diese Paare -1.

Weiterführende Frage

Nachdem du die Tabelle erstellt hast, wird eine Kante günstiger. Kannst du jede Distanz in O(n²) aktualisieren, statt die O(n³)-Schleifen erneut auszuführen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Du brauchst den kürzesten Pfad für jedes Knotenpaar. Floyd-Warshall findet alle n² Antworten mit einer dreifach verschachtelten Schleife. In jeder Runde können Routen an einem weiteren Knoten Halt machen, und pro Paar ist ein Vergleich nötig: die bisher beste Route mit der Route über den neuen Knoten.

Erweitere jede Route um eine Kante, bis sich nichts mehr ändert

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Beginne mit der Matrix und erweitere in jedem Durchlauf jeden Pfad um eine Kante: Ein Pfad von i nach m plus die Kante m → j ist ein Pfad von i nach j, der beibehalten wird, wenn er kürzer ist. Wiederhole dies, bis sich in einem Durchlauf nichts mehr ändert.

Nach p Durchläufen ist jeder kürzeste Pfad mit bis zu p+1 Kanten gefunden. Kein Gewicht ist negativ, also gibt es einen kürzesten Pfad ohne Schleife und mit höchstens n-1 Kanten, und die Durchläufe enden, sobald alle Distanzen endgültig sind. Ein Durchlauf umfasst bei 100 Knoten n³ = 10^6 Schritte, und eine lange Kette kürzester Pfade benötigt bis zu n Durchläufe: O(n⁴), bis zu 10^8 Schritte.

Algorithmus

Kopiere matrix nach dist.
Für jedes i, m und j: Wenn sowohl dist[i][m] als auch matrix[m][j] existieren, berechne ihre Summe.
Wenn dist[i][j] -1 ist oder größer als die Summe, speichere die Summe und merke dir, dass sich beim Durchlauf etwas geändert hat.
Wiederhole den Durchlauf, bis sich nichts mehr ändert, und gib dann dist zurück.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Floyd-Warshall: pro Runde einen weiteren Zwischenstopp zulassen

Idee

Schränke ein, an welchen Knoten eine Route zwischen ihren Endpunkten halten darf. Die Tabelle beginnt als Matrix der Routen ohne Zwischenhalte. Nach Runde k ist dist[i][j] die kürzeste Route, deren Zwischenhalte alle unter den Knoten 0 bis k liegen, und die letzte Runde liefert die Antwort.

In Runde k überspringt die beste Route, die auch bei k halten darf, entweder k – dann steht sie bereits in der Tabelle – oder sie führt genau einmal über k, da kein Gewicht negativ ist. Ihre beiden Hälften halten nur an Knoten von 0 bis k-1; daher sind sie dist[i][k] und dist[k][j].

Im ersten Beispiel ersetzt Runde 1 die direkte Route mit Gewicht 11 von Knoten 0 zu Knoten 2 durch eine Route mit Gewicht 6. In Runde 2 ergibt sich für die Route von Knoten 0 zu Knoten 3 ein Gewicht von 6 + 3 = 9; der Zwischenhalt bei Knoten 1 liegt innerhalb der Route mit Gewicht 6.

Eine Tabelle genügt: Zeile k und Spalte k ändern sich in Runde k nicht, da dist[k][k] 0 ist.

Algorithmus

Kopiere matrix nach dist; -1 bedeutet, dass noch keine Route gefunden wurde.
Für k von 0 bis n-1 und für jedes i und j: Überspringe das Paar, wenn dist[i][k] oder dist[k][j] -1 ist.
Berechne andernfalls via = dist[i][k] + dist[k][j].
Wenn dist[i][j] -1 oder größer als via ist, setze den Wert auf via.
Gib dist zurück.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

Stolperfallen und Grenzfälle

-1 als Gewicht behandeln: -1 + 5 = 4 sieht wie ein Weg aus. Prüfe zuerst beide Teile und behandle ein -1 in dist[i][j] als schlechter als jeden Weg.
Die Schleife über k nach innen setzen. Wege über Zwischenstopps 0 bis k-1 müssen endgültig feststehen, bevor Knoten k angeboten wird.
Die größte int-Zahl als Unendlich verwenden: Beim Addieren zweier solcher Zahlen läuft ein 32-Bit-int über und wird zu einer negativen Distanz. Eine tatsächliche Distanz beträgt höchstens 99 × 1000 = 99,000, daher ist 10^9 sicher, da 2 × 10^9 kleiner als 2^31-1 ist.
Annehmen, dass Kanten in beide Richtungen verlaufen. Im zweiten Beispiel erreicht Knoten 0 Knoten 1, aber von Knoten 1 aus ist kein Knoten erreichbar.
Eine Breitensuche ausführen, die Gewichte ignoriert: Im ersten Beispiel meldet sie 11 von Knoten 0 zu Knoten 2 statt 6.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität des Floyd-Warshall-Algorithmus?

O(n³) Zeit für n Knoten: drei verschachtelte Schleifen über die Knoten, mit einer Addition und einem Vergleich pro Schritt, 10^6 Schritte für 100 Knoten. Der Speicherbedarf beträgt O(n²) für die Entfernungstabelle, die direkt aktualisiert werden kann.

Funktioniert Floyd-Warshall mit negativen Kantengewichten?

Ja, solange es keinen negativen Zyklus gibt, also einen Zyklus, dessen Kantengewichte sich zu einem Wert kleiner als 0 addieren. Bei einem negativen Zyklus sind kürzeste Wege nicht definiert, und die Tabelle zeigt das: Für einige dist[i][i]-Werte ist das Ergebnis kleiner als 0.

Wann solltest du Floyd-Warshall statt des Dijkstra-Algorithmus verwenden?

Verwende Floyd-Warshall für jedes Knotenpaar in einem dichten Graphen mit bis zu einigen hundert Knoten. Dijkstra von jedem Knoten aus benötigt mit einem Array O(n³) und mit einem Heap O(n · E log n) und ist bei großen dünn besetzten Graphen schneller. Floyd-Warshall benötigt keinen Heap und unterstützt negative Kanten, Dijkstra hingegen nicht.

def shortestDistances(matrix):
    # Schreibe hier den Code

Test #1

Test #2

Argument

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

Erwartete Ausgabe

[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]