Bellman-Ford-Algorithmus

Der Algorithmus von Bellman und Ford (nach seinen Erfindern Richard Bellman und Lester Ford) ist ein Algorithmus der Graphentheorie und dient der Berechnung der kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen. Gelegentlich wird auch vom Moore-Bellman-Ford-Algorithmus gesprochen, da auch Edward F. Moore zu seiner Entwicklung beigetragen hat.

Anders als beim Algorithmus von Dijkstra, dem bekanntesten Verfahren zur Suche nach kürzesten Wegen in Graphen, dürfen hier die Gewichte der Kanten auch negativ sein. Kreise negativen Gewichtes, die vom Startknoten aus erreichbar sind, müssen jedoch ausgeschlossen werden, denn andernfalls könnten diese beliebig oft durchlaufen und somit Wege immer geringeren Gewichts konstruiert werden, es gäbe also überhaupt keinen Weg geringsten Gewichts.^[1] Der Bellman-Ford-Algorithmus kann das Vorhandensein von Kreisen negativen Gewichtes erkennen.

Algorithmus

G bezeichnet den gewichteten Graphen mit der Knotenmenge V und der Kantenmenge E. Gewicht gibt das Gewicht einer Kante zwischen zwei Knoten an. s ist der Startknoten, von dem ausgehend die kürzesten Wege zu allen anderen Knoten berechnet werden, und n ist die Anzahl der Knoten in V.

Wenn die Ausführung des Algorithmus endet, kann der Ausgabe entnommen werden, ob G einen Kreis negativer Länge besitzt. Falls dies nicht der Fall ist, enthält Distanz für jeden Knoten seinen Abstand zu s, also das Gewicht eines von s ausgehenden kürzesten Weges. Durch Vorgänger wird zudem ein Spannbaum definiert, der die von s ausgehenden kürzesten Wege in Form eines Out-Trees speichert. Ausgehend von einem Knoten kann man darin den entsprechenden kürzesten Weg rückwärts ermitteln, indem man rekursiv so lange den Knoten besucht, der durch Vorgänger gegeben ist, bis man s erreicht hat.

01  für jedes v aus V                   
02      Distanz(v) := unendlich, Vorgänger(v) := keiner
03  Distanz(s) := 0

04  wiederhole n - 1 mal               
05      für jedes (u,v) aus E
06          wenn Distanz(u) + Gewicht(u,v) < Distanz(v)
07          dann
08              Distanz(v) := Distanz(u) + Gewicht(u,v)
09              Vorgänger(v) := u

10  für jedes (u,v) aus E                
11      wenn Distanz(u) + Gewicht(u,v) < Distanz(v) dann
12          STOPP mit Ausgabe "Es gibt einen Kreis negativen Gewichtes."

13  Ausgabe Distanz

Im k-ten Schleifendurchlauf (04 – 09) wird zu jedem Knoten x ein kürzester s-x-Weg mit maximal k Kanten gefunden oder ein kürzerer Weg mit mehr Kanten. Ein Weg ohne Kreise enthält maximal n Knoten, also n − 1 Kanten. Falls in (10 – 12) festgestellt wird, dass ein Weg nicht optimal ist, muss dieser folglich einen Kreis mit negativem Gewicht enthalten.

Komplexität

Die Laufzeit des Algorithmus ist in $\mathcal{O} \left( n \cdot m \right)$, wobei n die Anzahl der Knoten und m die Anzahl der Kanten im Graphen sind. Wendet man den Algorithmus an, um kürzeste Wege von jedem Knoten zu jedem anderen Knoten zu finden, so beträgt die Komplexität $\mathcal{O} \left( n^2 \cdot m \right)$.

Anwendungen

Der Bellman-Ford-Algorithmus findet unter anderem im Distanzvektoralgorithmus, einem dynamischen Routing-Algorithmus, Verwendung. Dieser wird z. B. vom Routing Information Protocol eingesetzt, mit dem Routingtabellen innerhalb einer administrativen Netzwerkdomain dynamisch erstellt werden (Interior Gateway Protocol).

Andere Verfahren zur Berechnung kürzester Wege

Schneller als der Bellman-Ford-Algorithmus ist der Algorithmus von Dijkstra, ein Greedy-Algorithmus zur Suche kürzester Wege, der sukzessive den jeweils nächstbesten Knoten aus einer Priority Queue in eine Ergebnismenge S aufnimmt. Sein Nachteil besteht jedoch darin, dass er als Eingabe nur Graphen mit nichtnegativen Gewichten zulässt. Der A*-Algorithmus erweitert den Algorithmus von Dijkstra um eine Abschätzfunktion. Ein anderes Verfahren zur Suche kürzester Wege, das wie der Bellman-Ford-Algorithmus auf Dynamischer Programmierung beruht, ist der Floyd-Warshall-Algorithmus. Beide stützen ihre Korrektheit auf das Optimalitätsprinzip von Bellman.

Einzelnachweise

1. ↑ Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. 2. Auflage. Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8, S. 585-586.

Literatur

• L. R. Ford: Network flow theory, Paper P-923. The Rand Corporation, Santa Monica 1956
• R. E. Bellman: On a Routing Problem. In: Quarterly of Applied Mathematics. 16(1)/1958. Brown University, S. 87-90, ISSN 0033-569X
• E. F. Moore: The shortest path through a maze. In: Proceedings of the International Symposium on the Theory of Switching. 2/1959. Harvard University Press, S. 285-292
• L. R. Ford, D. R. Fulkerson: Flows in Networks., Princeton University Press, Princeton 1962, ISBN 0-691-07962-5
• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. 2. Auflage. Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8, Kapitel 24 und 25.

Weblinks

• Ein interaktives Java-Applet zur Demonstration