Floyd-Warshall für alle Paare

Manchmal benötigen Sie den kürzesten Weg zwischen jedem Knotenpaar und nicht nur von einem Startknoten aus. Das ist das Problem der kürzesten Wege zwischen allen Knotenpaaren.

Floyd-Warshall füllt mit drei übersichtlichen verschachtelten Schleifen eine vollständige Entfernungstabelle für alle Knotenpaare – und benötigt kaum Vorbereitung.

Verwenden Sie eine Matrix, in der dist[i][j] die bisher beste bekannte Entfernung von i nach j angibt. Initialisieren Sie sie mit den vorgegebenen direkten Kanten.

Jeder Knoten kann kostenlos sich selbst erreichen. Setzen Sie daher die Diagonale dist[i][i] vor Beginn der Relaxationen auf null.

Der Trick: Erlauben Sie Wegen, über einen Zwischenknoten k zu führen, und prüfen Sie dann, ob der Weg über k günstiger ist als der direkte Weg.

Die äußere Schleife ist k, der ausgewählte Mittelpunkt. Die inneren Schleifen über i und j prüfen jedes Knotenpaar mit diesem Mittelpunkt.

Relaxieren Sie für jedes Paar über k: Wenn der Weg von i über k nach j kürzer ist, aktualisieren Sie dist[i][j] auf diese Summe.

Wenn k abgeschlossen ist, dürfen alle Paare Zwischenknoten bis einschließlich k verwenden. Wenn k die äußerste Schleife bildet, bleibt diese Voraussetzung korrekt erhalten.

Floyd-Warshall akzeptiert negative Kanten, aber keine negativen Zyklen. Ein negativer Zyklus führt dazu, dass ein Diagonaleintrag kleiner als null wird.

Drei Schleifen über n Knoten ergeben eine Laufzeit von O(n^3) und einen Speicherbedarf von O(n^2). Das ist nur praktikabel, wenn n bei einigen Hundert bleibt.

Wählen Sie Floyd-Warshall, wenn der Graph klein und dicht ist und Sie tatsächlich die Entfernungen für jedes Knotenpaar benötigen, nicht nur die von einem Startknoten.

Welche Schleife muss bei Floyd-Warshall die äußerste sein?

Initialisieren Sie eine Matrix, setzen Sie die Diagonale auf null und durchlaufen Sie anschließend k, i, j, wobei Sie über k relaxieren. Kürzeste Wege zwischen allen Knotenpaaren in O(n^3). 🧮