Bellman-Ford-Algorithmus
Bellman-Ford-Algorithmus Definition
Der Bellman-Ford-Algorithmus findet den kürzesten Weg in Graphen.
Der Algorithmus wird vor allem eingesetzt, wenn es auch negative Kantengewichte bzw. Kosten gibt (mit diesen kann der Dijkstra-Algorithmus nicht umgehen).
Ausgangspunkt
- Gerichteter Graph (also Pfeile von einem Knoten zum anderen, keine Verbindung in beide Richtungen; sozusagen Einbahnstraßen statt normale Straßen) mit positiven oder negativen Kantengewichten;
- Keine negativen Zyklen (diese werden aber durch den Algorithmus entdeckt; deshalb sind ungerichtete Graphen mit negativen Kantengewichten nicht möglich).
Beispiel
Beispiel: Bellman-Ford-Algorithmus
Ein Graph umfasst die 3 Knoten bzw. Städte Aachen, Berlin und Celle, die im folgenden mit ihren Anfangsbuchstaben abgekürzt werden.
Die Städte sind durch folgende Einbahnstraßen (also nur in eine Richtung befahrbar) verbunden.
Hans aus Aachen möchte seinen Onkel in Berlin besuchen. Wenn er direkt nach Berlin fährt, kostet ihn das 100 € Benzin usw.; er könnte aber auch über Celle fahren (Kosten: bis Celle: 200 €) und von dort einen Arbeitskollegen nach Berlin mitnehmen. Der zahlt dafür so viel, dass Hans auf der Strecke 150 € Gewinn macht bzw. negative Kosten in der Höhe hat.
A – B: 100 €
A - C: 200 €
C - B: -150 €
Was ist für Hans der günstigste Weg von Aachen nach Berlin?
Man sieht hier natürlich leicht, dass die Direktfahrt nach Berlin 100 € kostet, während der Weg über Celle in Summe nur 200 € + (-150 €) = 50 € kostet und damit optimal ist.
Der Ford-Bellman-Algorithmus löst das in mehreren Iterationen (Durchgängen) – auch für größere Graphen – so:
Beginn
Man setzt zu Beginn die Kosten für den Startknoten A auf 0 (von A nach A kostet nichts) und die Kosten zu den anderen Knoten – vorübergehend – auf unendlich.
A: 0
B: unendlich
C: unendlich
Anschließend wird für jede Kante geprüft, ob die Kosten des Anfangsknotens der Kante zuzüglich der Kosten der Kante geringer sind als die Kosten des Endknotens der Kante.
1. Iteration
1. Kante:
A - B: 0 + 100 = 100
Das ist weniger als unendlich; für den Endknoten B wird deshalb notiert:
B: 100, A (100 € Kosten, Vorgänger: Knoten A)
2. Kante:
C - B: unendlich + (-150)
Das ist aufgrund der unendlichen Kosten von C uninteressant.
3. Kante:
A - C: 0 + 200 = 200
Das ist weniger als unendlich; für den Endknoten C wird deshalb notiert:
C: 200, A (200 € Kosten, Vorgänger: Knoten A)
2. Iteration
1. Kante:
A - B: 0 + 100 = 100
Also keine Änderung im 2. Durchgang.
B: 100, A (100 € Kosten, Vorgänger: Knoten A)
2. Kante:
C - B: 200 + (-150) = 50
Das ist weniger als bisher; für den Endknoten B wird deshalb notiert:
B: 50, C (50 € Kosten, Vorgänger: Knoten C)
3. Kante:
A - C: 0 + 200 = 200
Also keine Änderung im 2. Durchgang.
C: 200, A (200 € Kosten, Vorgänger: Knoten A)
Ende
Die Anzahl der Iterationen ist: Anzahl der Knoten - 1, also hier 3 - 1 = 2.
Ein negativer Zyklus ist nicht aufgetreten.
Der Zielknoten B hat (50, C) und damit C als Vorgängerknoten gespeichert; man geht also zu C und dort ist A als Vorgängerknoten gespeichert; von C geht es also zu A und damit zum Anfangsknoten.
Der optimale Weg mit den geringsten Kosten von A nach B ist: von A über C nach B.