Bellman-Ford-Algorithmus

Ein Beispielgraph, in dem eine Kante negatives Gewicht hat; diese Kante ist farblich hervorgehoben.

Der Bellman-Ford-Algorithmus ist ein Algorithmus, der kürzeste Wege in einem Graphen findet. Anders als der Dijkstra-Algorithmus kann der Bellman-Ford-Algorithmus jedoch auch mit negativen Kantengewichten umgehen.

Das Problem

Betrachten wir den nebenstehenden Beispielgraphen, in dem eine Kante negatives Gewicht hat. Der kürzeste Weg von A nach D führt über B und hat die Länge -2. Der Dijkstra-Algorithmus würde aber den Weg über C präferieren, der die Länge 3 hat. Der Dijkstra-Algorithmus ist nämlich greedy und betrachtet immer nur die nächstbeste Kante mit minimalem Gewicht. Bei Graphen mit ausschließlich positiven Kantengewichten ist das kein Problem, da die Gesamtlänge eines Weges immer nur größer werden kann. Bei Graphen, in denen auch negative Kantengewichte vorkommen, dagegen schon, da es hier auch vorteilhaft sein kann, zunächst größere Kantengewichte in Kauf zu nehmen, wenn diese später durch negative Kantengewichte ausgeglichen werden können.

Der Algorithmus

Gegeben seien:

• ein Graph G mit n Knoten
• ein Startknoten s, von dem aus alle kürzesten Wege berechnet werden sollen

Zu jedem Knoten im Graph wird nun seine Distanz zum Startknoten s gespeichert sowie der direkte Vorgänger auf dem Weg zu s. Durch die Vorgänger kann man sich so den kürzesten Weg zu s erarbeiten.

Der Algorithmus läuft folgendermaßen ab:

• Zu Beginn des Algorithmus wird für jeden Knoten die Distanz auf $\infty$ gesetzt, außer für s, dessen Distanz auf 0 gesetzt wird.
• Dann wird n-1 Mal durch alle Kanten durchiteriert und für jede Kante x—y Folgendes geprüft:
  • Ist Distanz s—x + Kante x—y < Distanz s—y?
    • Falls ja, setze Distanz s—y := Distanz s—x + Kante x—y Vorgänger von y := x
• Zuletzt wird nochmal durch alle Kanten durchiteriert und für jede Kante x—y dieselbe Bedingung geprüft:
  • Ist Distanz s—x + Kante x—y < Distanz s—y?
    • Falls ja, ...?

Weblinks

• Visualisierung auf VisuAlgo.net 🇬🇧