AlgorithmsGraph AlgorithmsArtikel

Floyd-Warshall: All-Pairs Shortest Paths mit Dynamic Programming

Praxisnaher Leitfaden zu Floyd-Warshall mit Distanzmatrix, Path Reconstruction, negativen Gewichten und Transitive Closure.

21. August 20269 Min. Lesezeit7 Aufrufe

#Graph#Algorithms#Floyd-Warshall#Dynamic Programming#Shortest Path#JavaScript#TypeScript

Arian Soleimanzadeh

Software Engineer & Researcher

Visueller Leitfaden zu Floyd-Warshall und All-Pairs Shortest Paths

Arian Soleimanzadeh

KI · Code · Produkt

Forschung + Engineering

Auf dieser Seite

Floyd-Warshall berechnet All-Pairs Shortest Paths mit Dynamic Programming.

Die zentrale Rekurrenz lautet:

Code

dist[i][j] =
min(
  dist[i][j],
  dist[i][k] + dist[k][j]
)

Für jeden Zwischenknoten k wird geprüft, ob der Weg i → k → j besser ist.

Initialisierung

Code

dist[i][i] = 0

Direkte Kanten erhalten ihr Gewicht, fehlende Verbindungen Infinity.

Negative Gewichte

Negative Kanten sind erlaubt.

Ein negativer Diagonaleintrag:

Code

dist[i][i] < 0

zeigt einen negativen Zyklus.

Path Reconstruction

Eine zusätzliche next-Matrix kann den ersten Schritt des jeweils besten Pfads speichern.

Reachability

Mit Boolean-Operationen statt min/+ lässt sich die Transitive Closure berechnen.

Vergleich

Floyd-Warshall:

Code

All Pairs
O(V³)

Für große Sparse Graphs sind wiederholtes Dijkstra oder Johnson oft geeigneter.

Anwendungen

Routing-Matrizen
Logistik
Netzwerklatenzen
Reachability
Dependency-Analyse

Komplexität

Code

Zeit: O(V³)
Speicher: O(V²)

Fazit

Floyd-Warshall ist besonders nützlich, wenn alle Paar-Distanzen benötigt werden und die Knotenzahl moderat ist.

Vorheriger Artikel

Bellman-Ford: Negative Gewichte und Negative Cycles

Nächster Artikel

Prim's Algorithmus: MST, Min-Heap und Cut Property

AlgorithmsGraph AlgorithmsArtikel

Floyd-Warshall: All-Pairs Shortest Paths mit Dynamic Programming

Praxisnaher Leitfaden zu Floyd-Warshall mit Distanzmatrix, Path Reconstruction, negativen Gewichten und Transitive Closure.

21. August 20269 Min. Lesezeit7 Aufrufe

#Graph#Algorithms#Floyd-Warshall#Dynamic Programming#Shortest Path#JavaScript#TypeScript

Arian Soleimanzadeh

Software Engineer & Researcher

Arian Soleimanzadeh

KI · Code · Produkt

Forschung + Engineering

Auf dieser Seite

Floyd-Warshall berechnet All-Pairs Shortest Paths mit Dynamic Programming.

Die zentrale Rekurrenz lautet:

Code

dist[i][j] =
min(
  dist[i][j],
  dist[i][k] + dist[k][j]
)

Für jeden Zwischenknoten k wird geprüft, ob der Weg i → k → j besser ist.

Initialisierung

Code

dist[i][i] = 0

Direkte Kanten erhalten ihr Gewicht, fehlende Verbindungen Infinity.

Negative Gewichte

Negative Kanten sind erlaubt.

Ein negativer Diagonaleintrag:

Code

dist[i][i] < 0

zeigt einen negativen Zyklus.

Path Reconstruction

Eine zusätzliche next-Matrix kann den ersten Schritt des jeweils besten Pfads speichern.

Reachability

Mit Boolean-Operationen statt min/+ lässt sich die Transitive Closure berechnen.

Vergleich

Floyd-Warshall:

Code

All Pairs
O(V³)

Für große Sparse Graphs sind wiederholtes Dijkstra oder Johnson oft geeigneter.

Anwendungen

Routing-Matrizen
Logistik
Netzwerklatenzen
Reachability
Dependency-Analyse

Komplexität

Code

Zeit: O(V³)
Speicher: O(V²)

Fazit

Floyd-Warshall ist besonders nützlich, wenn alle Paar-Distanzen benötigt werden und die Knotenzahl moderat ist.

Vorheriger Artikel

Bellman-Ford: Negative Gewichte und Negative Cycles

Nächster Artikel