Bellman-Ford-Algorithmus
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 Pfade ausgehend von einem Startknoten in einem kantengewichteten Graphen. Die Gewichte können dabei auch negativ sein.
Kreise 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 Kreise negativer Länge zu erkennen.
Falls ein Knoten vom Startknoten nicht erreichbar ist, ist sein Abstand unendlich.
Algorithmus
G bezeichnet den gewichteten Graphen mit V als Knotenmenge, E als Kantenmenge und Kosten 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 Kreis 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 //Initialisierung 02 Distanz(v) := unendlich, Vorgänger(v) := kein 03 Distanz(s) := 0 04 wiederhole n - 1 mal //Berechnung der Distanzen 05 für jedes (u,v) aus E 06 wenn Distanz(u) + Kosten(u,v) < Distanz(v) 07 dann 08 Distanz(v) := Distanz(u) + Kosten(u,v) 09 Vorgänger(v) := u 10 für jedes (u,v) aus E //Kontrolle auf negative Distanzen 11 wenn Distanz(u) + Kosten(u,v) < Distanz(v) dann 12 STOP mit Ausgabe "Kreis negativer Länge gefunden" 13 Ausgabe Distanz
Grundlegende Konzepte und Verwandschaften
Im k-ten Schleifendurchlauf (04 - 09) wird der Abstand des kürzesten Weges mit maximal k Kanten berechnet. 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 er einen Kreis mit negativem Gewicht enthalten.
Der Algorithmus von Dijkstra ist ein Greedy Algorithmus zur Suche kürzester Pfade, der sukzessive den nächstbesten Knoten, der einen kürzesten Pfad besitzt, in eine Ergebnismenge aufnimmt. Der A*-Algorithmus erweitert den Algorithmus von Dijkstra um eine Abschätzfunktion.
Ein Algorithmus zur Suche kürzester Pfade, der sich jedoch auf das Optimalitätsprinzip von Bellman stützt, ist der Floyd-Warshall-Algorithmus.
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.