Bellman-Ford berechnet Single-Source Shortest Paths und unterstützt negative Kantengewichte.
Außerdem kann der Algorithmus einen vom Startknoten erreichbaren negativen Zyklus erkennen.
Relaxation
Für eine Kante:
u → v mit Gewicht wgilt:
wenn dist[u] + w < dist[v]
→ dist[v] aktualisierenAlle Kanten werden bis zu V-1 Mal relaxiert.
Warum V-1?
Ein einfacher kürzester Pfad enthält höchstens V-1 Kanten, sofern kein relevanter negativer Zyklus existiert.
Negative Cycle
Nach den V-1 Durchläufen erfolgt ein zusätzlicher Test.
Ist noch eine Relaxation möglich, existiert ein erreichbarer negativer Zyklus.
Bellman-Ford vs Dijkstra
Bellman-Ford:
- negative Gewichte erlaubt
- Negative-Cycle-Erkennung
O(VE)
Dijkstra:
- normalerweise nur nichtnegative Gewichte
- meist deutlich schneller
Anwendungen
- Distance-Vector-Routing
- Difference Constraints
- Credit/Penalty-Modelle
- Negative-Cycle-Erkennung
- gewichtete Dependency-Modelle
Optimierung
Wenn ein kompletter Durchlauf keine Aktualisierung erzeugt, kann der Algorithmus früh beendet werden.
Komplexität
Zeit: O(VE)
Speicher: O(V)Fazit
Bellman-Ford ist besonders dann sinnvoll, wenn negative Gewichte möglich sind und Dijkstra daher nicht zuverlässig eingesetzt werden kann.