Bellmann-Ford-Algorithmus

Der Bellmann-Ford-Algorithmus ist ein Algorithmus zur Berechnung kürzester Wege von einem Knoten zu allen anderen Knoten in gewichteten Graphen. Anders als beim Dijkstra-Algorithmus, dürfen Kanten hier auch negativ gewichtet sein.

Idee

• Wir wissen, dass jeder kürzeste Weg in einem Graphen ein Pfad in einem Baum ist, d.h. er besteht höchstens aus Knoten
• Das Relaxationsprinzip wird also mal für jede Kante benutzt

Implementierung

Pseudocode

Seien ein gerichteter Graph, eine beliebige Gewichtung und eine Quelle.

• Algorithmus BellmanFord(, , ):
  • Für jeden Knoten :
    • .dist =
    • .pred = NULL
  • .dist = 0
  • Wiederhole mal:
    • Für jede Kante :
      • Falls .dist > .dist + :
        • .dist = .dist +
        • .pred =
  • Für jede Kante : Negativer Zyklus?
    • Falls .dist > .dist + :
      • return “Negativer Zyklus!”

Laufzeit

Da wir mal alle Kanten relaxieren, ist die Gesamtlaufzeit

Durch vorzeitiges Abbrechen der Schleife wenn sich keine Pfade mehr seit der letzten Iteration geändert haben, lässt sich die Laufzeit

erzielen.