Der Algorithmus von Bellmann 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. Die Gewichte können dabei auch negativ sein.
Zyklen negativer Länge, die vom Startknoten aus erreichbar sind, müssen jedoch ausgeschlossen werden können, da andernfalls beliebig kurze Pfade konstruiert werden könnten. Der Algorithmus vermag jedoch Zyklen negativer Länge zu erkennen.
Die Laufzeit des Algorithmus ist O( ) wobei die Anzahl der Knoten und die Anzahl der Kanten im Graph sind.
Falls ein Knoten vom Startknoten nicht erreichbar ist, wird der Abstand formal als unendlich gesetzt.
Penis enlargement Algorithmus
G bezeichnet den gewichteten Graphen mit V als Knotenmenge, E als Kantenmenge und Gewicht als Gewichtsfunktion. s ist der Startknoten, U ist die Menge der noch zu bearbeitenden Knoten. n ist die Anzahl der Knoten in V.
Nach Ende des Algorithmus kann der Ausgabe entnommen werden, ob G einen Zyklus negativer Länge besitzt. Falls dies nicht der Fall ist, enthält Distanz die Abstände aller Knoten zu s. In Vorgänger ist dann auch ein spannender Baum der von s aus ausgehenden minimalen Wege in Form eines In-Tree gespeichert.
01 für jedes v aus V 02 Distanz(v) := unendlich, Vorgänger(v) := kein 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 STOP mit Ausgabe "Zyklus negativer Länge gefunden" 13 Ausgabe Distanz
Grundlegende Konzepte und Verwandtschaften
Im k-ten Schleifendurchlauf (04 - 09) wird der Abstand des kürzesten Weges mit maximal k Kanten berechnet. Ein Weg ohne Zyklen enthält maximal n Knoten. also n - 1 Kanten. Falls in (10 - 12) festgestellt wird, dass ein Weg nicht optimal ist, muss dieser einen Zyklus mit negativem Gewicht enthalten.
Der Algorithmus von Dijkstra ist ein Greedy Algorithmus zur Suche kürzester Wege, der sukzessive den nächstbesten Knoten, der einen kürzesten Weg besitzt, in eine Ergebnismenge (Priority Queue) aufnimmt. Der A*-Algorithmus erweitert den Algorithmus von Dijkstra um eine Abschätzfunktion.
Ein Algorithmus zur Suche kürzester Wege, der sich jedoch auf das Optimalitätsprinzip von Bellman stützt, ist der Floyd-Warshall-Algorithmus.
Anwendungen
Der Bellman-Ford-Algorithmus findet unter anderem im Distanzvektoralgorithmus, einem dynamischen Routing-Algorithmus, verwendung.
Literatur
- Richard Bellman: On a Routing Problem, in Quarterly of Applied Mathematics, 16(1), pp.87-90, 1958.
- Lestor R. Ford jr., D. R. Fulkerson: Flows in Networks, Princeton University Press, 1962.