Bellman-Ford ist ein Algorithmus der Graphentheorie, der den kürzesten Weg von einem Startknoten zu allen anderen Knoten eines gewichteten Graphen berechnet. Seine besondere Stärke: Anders als der Dijkstra-Algorithmus kommt er auch mit negativen Kantengewichten zurecht.
Wie funktioniert Bellman-Ford?
Der Algorithmus startet mit dem Abstand 0 am Startknoten und unendlich an allen übrigen Knoten. Anschließend wird in bis zu V-1 Durchläufen (V = Anzahl der Knoten) jede Kante relaxiert: Ist der Abstand zum Zielknoten über die Kante kürzer als der bisher gespeicherte Wert, wird er aktualisiert. Nach V-1 Runden ist der kürzeste Weg gefunden, denn ein kürzester Pfad ohne Zyklen kann höchstens V-1 Kanten enthalten.
Negative Kantengewichte und negative Zyklen
Negative Kantengewichte treten in der Praxis auf, etwa bei Kostenmodellen mit Rabatten oder Guthaben. Ein negativer Zyklus ist eine Rundtour, deren Gesamtgewicht negativ ist — dann gibt es keinen endlichen kürzesten Weg, weil man die Schleife beliebig oft durchlaufen und den Abstand immer weiter senken kann. Bellman-Ford erkennt solche Zyklen: Verbessert sich im V-ten Durchlauf noch ein Abstand, existiert ein negativer Zyklus, den der Algorithmus meldet.
Laufzeit und Praxis
Die Laufzeit beträgt O(V·E) und ist damit höher als bei Dijkstra (O((V+E)·log V)). Dafür ist Bellman-Ford allgemeiner einsetzbar. Typische Anwendungen sind Distance-Vector-Routing-Protokolle wie RIP in Netzwerken sowie die Erkennung negativer Zyklen in Wirtschafts- und Finanzmodellen. Der Algorithmus wurde unabhängig von Richard Bellman und Lester Ford Jr. entwickelt und ist eng mit der dynamischen Programmierung verwandt — die Relaxation der Kanten folgt demselben Prinzip wie das Lösen überlappender Teilprobleme. Als Datenstruktur genügt die Adjazenzliste oder Adjazenzmatrix des Graphen.
Kurz zusammengefasst
- Kürzeste Wege von einem Startknoten aus, auch mit negativen Kantengewichten
- Prinzip: V-1 Runden Kanten-Relaxation, danach Zyklus-Erkennung
- Laufzeit O(V·E), robuster als Dijkstra, dafür langsamer
- Grundlage von Routing-Protokollen wie RIP