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 gerichteten 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:

1. Zu Beginn des Algorithmus wird für jeden Knoten k die Distanz[k] auf $\infty$ und der Vorgänger[k] auf null gesetzt, außer für s, dessen Distanz auf 0 gesetzt wird.
2. Wiederhole n-1 Mal:
   1. Prüfe für jede Kante x—y:
      1. Ist Distanz[x] + Kantenlänge x—y < Distanz[y]?
         1. Falls ja, setze Distanz[y] := Distanz[x] + Kante x—y…
         2. … und setze Vorgänger[y] := x
3. Zuletzt wird nochmal durch alle Kanten durchiteriert und für jede Kante x—y dieselbe Bedingung geprüft:
   1. Ist Distanz[x] + Kante x—y < Distanz[y]?
      1. Falls ja, dann enthält der Graph einen Kreis negativer Länge. In diesem Fall können durch wiederholtes Durchlaufen dieses Kreises beliebig kurze Wege erzeugt werden und es kann keine kürzesten Wege geben.
      2. Falls nein, sind die kürzesten Wege gefunden und die Distanzen und Vorgänger werden zurückgegeben.

Beispiel

🕳

Lückenhaft

In diesem Artikel oder Abschnitt fehlen noch wichtige Informationen.

Hilf dem KGS-Wiki, indem du sie recherchierst und einfügst.

Weblinks

• "Der Bellman-Ford-Algorithmus visualisiert" auf VisuAlgo.net 🇬🇧🇨🇳🇮🇩
• Erklärung und interaktives Beispiel der TU München

Algorithmen auf Graphen

Suche: Breitensuche | Tiefensuche

Kürzeste Wege: Dijkstra-Algorithmus | Bellman-Ford-Algorithmus

Minimale Spannbäume: Kruskal-Algorithmus | Prim-Algorithmus | Borůvka-Algorithmus