Der Bellman-Ford-Algorithmus erklärt

Mohammed Islam Hadjoudj

Experte für Operations Research

1. Einführung in den Bellman-Ford-Algorithmus

Der Bellman-Ford-Algorithmus ist einer der grundlegendsten Algorithmen der Graphentheorie. Benannt nach seinen Pionieren Richard Bellman und Lester Ford Jr., die ihn in den 1950er Jahren veröffentlichten, löst dieser Algorithmus das Single-Source-Kürzeste-Wege-Problem. Das bedeutet, er findet den kürzesten Weg von einem Startknoten zu allen anderen Knoten in einem gewichteten Graphen.

Wenn Sie mit dem Dijkstra-Algorithmus vertraut sind, fragen Sie sich vielleicht: "Warum brauchen wir einen weiteren Algorithmus für genau dasselbe Problem?" Die Antwort liegt in der Vielseitigkeit. Der Dijkstra-Algorithmus ist zwar schneller und äußerst effizient für Graphen, in denen alle Kantengewichte positiv sind (wie physische Straßennetze), versagt aber vollständig, sobald negative Kantengewichte ins Spiel kommen. Bellman-Ford hingegen kommt mit negativen Gewichten zurecht und bietet einen robusten Mechanismus dafür, sodass auch in komplexen wirtschaftlichen oder Netzwerkszenarien korrekte kürzeste Wege berechnet werden.

Darüber hinaus besitzt Bellman-Ford eine einzigartige Superkraft: Es kann negative Zyklen erkennen. Ein negativer Zyklus ist eine Schleife in einem Graphen, in der die Summe der Kantengewichte kleiner als null ist. Existiert ein solcher Zyklus, wird das Konzept des "kürzesten Weges" bedeutungslos, da man den Zyklus theoretisch unendlich oft durchlaufen könnte, um eine Weglänge von minus unendlich zu erreichen. Bellman-Ford erkennt diese Anomalie und weist Sie darauf hin, was es zu einem unverzichtbaren Werkzeug für die Anomalieerkennung in verschiedenen Bereichen macht, einschließlich der Finanzarbitrage.

2. Das Problem mit Dijkstra: negative Gewichte

Um die Notwendigkeit des Bellman-Ford-Algorithmus wirklich zu verstehen, müssen wir zunächst die entscheidende Einschränkung des Dijkstra-Algorithmus betrachten.

Der Dijkstra-Algorithmus arbeitet nach einem gierigen Prinzip. Er verwaltet eine Menge unbesuchter Knoten und wählt in jedem Schritt den Knoten mit der kleinsten bekannten Distanz zur Quelle. Sobald ein Knoten ausgewählt ist, betrachtet Dijkstra dessen kürzeste Distanz als "endgültig" und besucht ihn nie wieder, um seine Distanz zu aktualisieren. Diese Annahme funktioniert einwandfrei, wenn alle Kantengewichte positiv sind, denn das Hinzufügen einer weiteren Kante zu einem Weg vergrößert stets die Gesamtweglänge. Daher könnte kein später entdeckter Weg kürzer sein als der aktuell endgültige.

Was aber passiert, wenn wir ein negatives Kantengewicht einführen?

Betrachten Sie einen einfachen Graphen mit drei Knoten: A, B und C. Der Startknoten ist A.

• Die Kante von A nach B hat ein Gewicht von 2.
• Die Kante von A nach C hat ein Gewicht von 3.
• Die Kante von C nach B hat ein Gewicht von -2.

Führen Sie den Dijkstra-Algorithmus von A aus. Er relaxiert zuerst die Nachbarn von A und gibt B die vorläufige Distanz 2 und C die vorläufige Distanz 3. Dann wählt er den kleinsten Wert, B mit 2, und legt ihn endgültig fest: Von diesem Moment an betrachtet Dijkstra B nie wieder. Erst danach legt er C mit 3 fest und relaxiert die ausgehende Kante von C, wobei er den Weg A -> C -> B mit dem Gesamtgewicht 3 + (-2) = 1 entdeckt. Das ist tatsächlich kürzer als 2, doch B wurde zwei Schritte zuvor festgeschrieben, also meldet der Algorithmus 2. Die wahre kürzeste Distanz zu B beträgt 1, und Dijkstra hat ein falsches Ergebnis geliefert.

Genau das ist der Fehler. Die gierige Regel von Dijkstra setzt voraus, dass ein Knoten mit der kleinsten vorläufigen Distanz durch nichts später Gefundenes mehr unterboten werden kann. Eine negative Kante bricht diese Annahme, denn ein längerer Anfang kann trotzdem zu einer kürzeren Gesamtstrecke führen.

Genau hier glänzt Bellman-Ford. Es verzichtet auf den gierigen Ansatz und relaxiert stattdessen systematisch alle Kanten mehrfach. So ist garantiert, dass der Algorithmus den kürzesten Weg auch dann korrekt erkennt und aktualisiert, wenn eine negative Kante erst später eine kürzere Abkürzung bietet.

3. Die Gefahr negativer Zyklen

Ein negativer Zyklus ist eine geschlossene Schleife in einem Graphen, in der die Summe der Gewichte der den Zyklus bildenden Kanten kleiner als null ist. Dieses Konzept ist grundlegend dafür, warum Bellman-Ford so konzipiert ist, wie es ist.

Stellen Sie sich einen Graphen mit den Knoten A, B und C vor, die ein Dreieck bilden. Die Kantengewichte sind A nach B (2), B nach C (-5) und C nach A (1). Das Gesamtgewicht dieses Zyklus beträgt 2 + (-5) + 1 = -2. Möchten Sie den kürzesten Weg von A zu einem beliebigen anderen Knoten finden, könnten Sie diesen Zyklus einfach unendlich oft umrunden. Jedes Mal, wenn Sie die Schleife abschließen, verringert sich Ihre Gesamtdistanz um 2. Nach einer Runde beträgt die Distanz -2, nach zehn Runden -20. Gegen unendlich strebt der kürzeste Weg gegen minus unendlich.

Bei einem vom Startknoten aus erreichbaren negativen Zyklus hat das Kürzeste-Wege-Problem keine Lösung. Standardalgorithmen gerieten in eine Endlosschleife und versuchten ständig, einen "kürzeren" Weg zu finden. Bellman-Ford vermeidet diese Endlosschleife elegant und erkennt das Vorhandensein des Zyklus ausdrücklich.

4. Kernkonzept: Kantenrelaxation

Die Grundlage des Bellman-Ford-Algorithmus ist ein Prozess namens Kantenrelaxation. Dies ist der Mechanismus, mit dem der Algorithmus die kürzeste bekannte Distanz zu einem Knoten aktualisiert.

Definieren wir zwei Arrays (oder Dictionaries):

• distance[]: Speichert die kürzeste bekannte Distanz vom Startknoten zu jedem anderen Knoten. Anfangs ist die Distanz zum Startknoten 0 und die Distanz zu allen anderen Knoten auf unendlich (∞) gesetzt.
• predecessor[] (optional, aber nützlich): Speichert den Knoten, der auf dem kürzesten Weg unmittelbar vor einem gegebenen Knoten liegt. Damit lässt sich der tatsächliche Weg rekonstruieren, sobald der Algorithmus fertig ist.

Die Relaxationsoperation für eine Kante vom Knoten u zum Knoten v mit Gewicht w ist wie folgt definiert:

if distance[u] + w < distance[v]:
    distance[v] = distance[u] + w
    predecessor[v] = u

Auf gut Deutsch: "Wenn die bekannte Distanz zum Knoten u plus das Gewicht der Kante von u nach v kleiner ist als die derzeit bekannte kürzeste Distanz zum Knoten v, dann haben wir einen besseren Weg gefunden! Aktualisiere die kürzeste Distanz zu v."

Der Bellman-Ford-Algorithmus durchläuft einfach alle Kanten des Graphen und versucht immer wieder, sie zu relaxieren.

5. Schrittweise Ausführung von Bellman-Ford

Gehen wir nun die genauen Schritte des Algorithmus durch.

Sei V die Anzahl der Ecken (Knoten) im Graphen und E die Anzahl der Kanten. Der Algorithmus verläuft in drei Hauptphasen.

Phase 1: Initialisierung

Initialisieren Sie das distance-Array. Setzen Sie die Distanz zum Startknoten auf 0 und die Distanz zu allen anderen Knoten auf unendlich. Das drückt aus, dass wir anfangs nicht wissen, wie wir einen anderen Knoten als den Start erreichen.

Phase 2: Wiederholte Relaxation

Das ist der Kern des Algorithmus. Wir müssen alle Kanten des Graphen relaxieren, und zwar V - 1 Mal.

Warum genau V - 1 Mal? Betrachten Sie einen Graphen mit V Knoten. Der längstmögliche einfache kürzeste Weg (ein Weg ohne Zyklen) zwischen zwei beliebigen Knoten kann höchstens V - 1 Kanten haben. Im schlimmsten Fall braucht es einen vollen Durchlauf über alle Kanten, um zu garantieren, dass Wege der Länge 1 Kante korrekt sind. Zwei Durchläufe garantieren Wege der Länge 2 Kanten, und so weiter. Nach V - 1 Durchläufen haben wir daher, sofern keine negativen Zyklen vorliegen, garantiert den absolut kürzesten Weg zu jedem Knoten gefunden, unabhängig von der Reihenfolge, in der wir die Kanten verarbeiten.

1. Starten Sie eine Schleife, die V - 1 Mal läuft.
2. Iterieren Sie innerhalb dieser Schleife über jede einzelne Kante des Graphen.
3. Versuchen Sie für jede Kante (u, v) mit Gewicht w, sie zu relaxieren: Wenn distance[u] + w < distance[v], aktualisieren Sie distance[v].

Phase 3: Erkennung negativer Zyklen

Nach Abschluss von Phase 2 haben wir die kürzesten Distanzen, sofern keine negativen Zyklen existieren. Um auf negative Zyklen zu prüfen, führen wir einen letzten, zusätzlichen Durchlauf über alle Kanten aus.

1. Iterieren Sie ein letztes Mal über jede Kante (u, v) mit Gewicht w.
2. Versuchen Sie, sie zu relaxieren. Wenn distance[u] + w < distance[v] IMMER NOCH wahr ist, bedeutet das, dass wir nach V - 1 Kanten einen noch kürzeren Weg gefunden haben.
3. Für einen einfachen Weg ist das mathematisch unmöglich. Die einzige Erklärung ist, dass wir in einen negativen Gewichtszyklus geraten sind, der es erlaubt, die Distanz unendlich zu verringern. Tritt dies auf, bricht der Algorithmus ab und meldet, dass ein negativer Zyklus existiert.

6. Implementierung und Pseudocode

Die Schönheit von Bellman-Ford liegt in seiner Einfachheit. Die Implementierung ist bemerkenswert unkompliziert, oft nur ein paar verschachtelte Schleifen. Hier ist der Standard-Pseudocode:

function BellmanFord(Graph, source):
    // Phase 1: Initialisierung
    distance = array of size |V|, filled with Infinity
    predecessor = array of size |V|, filled with Null
    distance[source] = 0

    // Phase 2: Alle Kanten |V| - 1 Mal relaxieren
    for i from 1 to |V| - 1:
        for each edge (u, v) with weight w in Graph:
            if distance[u] != Infinity and distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                predecessor[v] = u

    // Phase 3: Auf negative Gewichtszyklen prüfen
    for each edge (u, v) with weight w in Graph:
        if distance[u] != Infinity and distance[u] + w < distance[v]:
            return "Fehler: Graph enthält einen negativen Gewichtszyklus"

    return distance, predecessor

Dieser Code ist sprachunabhängig und lässt sich leicht in Python, C++, Java oder JavaScript übertragen.

Beachten Sie die Absicherung distance[u] != Infinity in beiden Phasen. Ohne sie wird über einen unerreichbaren Knoten hinweg relaxiert: Bei einer echten Gleitkomma-Unendlichkeit ist der Vergleich unschädlich, doch wenn Sie Unendlich durch einen großen Platzhalter wie INT_MAX darstellen, ist INT_MAX + w für negatives w kleiner als INT_MAX, und der Algorithmus erfindet Wege zu Knoten, die gar nicht erreichbar sind.

7. Analyse der Zeit- und Speicherkomplexität

Bellman-Ford ist zwar äußerst vielseitig, bringt aber im Vergleich zu gierigen Algorithmen einen Leistungsnachteil mit sich.

• Zeitkomplexität: Der Algorithmus lässt eine Schleife V - 1 Mal laufen und iteriert darin über alle E Kanten. Daher beträgt die Zeitkomplexität für Phase 2 O(V * E). Die Zykluserkennungsphase benötigt O(E). Die Gesamtzeitkomplexität ist O(V * E). In einem dichten Graphen, in dem E nahe bei V² liegt, nähert sich die Komplexität O(V³). Das macht ihn deutlich langsamer als den Dijkstra-Algorithmus, der mit einem Fibonacci-Heap O(V log V + E) erreichen kann.
• Speicherkomplexität: Der Algorithmus muss nur das distance-Array und das predecessor-Array speichern, beide der Größe V. Zudem muss der Graph selbst gespeichert werden. Die zusätzliche Speicherkomplexität beträgt daher O(V).

Wegen seiner Zeitkomplexität von O(V * E) wird Bellman-Ford typischerweise nur bei Bedarf eingesetzt, also wenn negative Gewichte vorliegen oder die Erkennung negativer Zyklen zwingend erforderlich ist. Für rein positive Graphen ist Dijkstra die bevorzugte Wahl.

8. Anwendungen in der Praxis

Obwohl er langsamer als Dijkstra ist, hat Bellman-Ford tiefgreifende praktische Anwendungen, insbesondere in Netzwerktechnik und Finanzwesen.

Routing Information Protocol (RIP)

In der Computervernetzung bestimmen Routing-Protokolle, wie Datenpakete durch das Internet reisen. Eines der frühesten und bekanntesten Protokolle, das Routing Information Protocol (RIP), ist ein Distanzvektor-Routing-Protokoll, das stark auf einer verteilten Variante des Bellman-Ford-Algorithmus beruht.

In diesem verteilten Aufbau haben Router keine vollständige Karte des gesamten Netzwerks. Stattdessen kennt jeder Router nur seine unmittelbaren Nachbarn. Router teilen ihren Nachbarn regelmäßig ihre Routing-Tabellen mit (ihre bekannten kürzesten Distanzen zu verschiedenen Zielen). Erhält ein Router ein Update, nutzt er die Bellman-Ford-Relaxationsgleichung, um seine eigene Routing-Tabelle zu aktualisieren. Mit der Zeit breitet sich diese Information im Netzwerk aus, sodass alle Router zu den kürzesten Wegen konvergieren.

Erkennung von Finanzarbitrage

Arbitrage ist die Praxis, eine Preisdifferenz zwischen zwei oder mehr Märkten auszunutzen. Im Devisenmarkt (Forex) schwanken die Wechselkurse. Eine Arbitragemöglichkeit besteht, wenn Sie mit einer Währung beginnen, sie über eine Folge anderer Währungen tauschen und am Ende mehr Ihrer Ausgangswährung besitzen als zu Beginn, ohne ein Marktrisiko einzugehen.

Wir können Wechselkurse als Graphen modellieren, in dem Knoten Währungen (USD, EUR, GBP usw.) sind und Kanten den Wechselkurs darstellen. Da wir Wechselkurse multiplizieren statt addieren, können wir den negativen Logarithmus der Kurse nehmen, um das Problem in ein additives umzuwandeln. Eine Arbitragemöglichkeit (bei der das Produkt der Kurse > 1 ist) verwandelt sich in unserem modifizierten Graphen in einen negativen Zyklus. Bellman-Ford auf diesem Graphen erkennt diese negativen Zyklen und identifiziert für algorithmische Händler sofort profitable Arbitrageschleifen.

9. Akademische Quellen und Geschichte

Der Bellman-Ford-Algorithmus wird manchmal als Bellman-Ford-Moore-Algorithmus bezeichnet. Tatsächlich gelangten vier Forscher innerhalb von fünf Jahren unabhängig voneinander zu ihm:

• Alfonso Shimbel (1955): Schlug den Algorithmus ursprünglich vor, wenngleich er weniger bekannt wurde.
• Lester Ford Jr. (1956): Entwickelte die grundlegenden Konzepte in "Network Flow Theory" (RAND Corporation Paper).
• Richard Bellman (1958): Formalisierte ihn in "On a routing problem" (Quarterly of Applied Mathematics).
• Edward F. Moore (1959): Veröffentlichte eine Variante des Algorithmus in "The shortest path through a maze" (Proceedings of the International Symposium on the Theory of Switching).

Dieser Algorithmus legte den Grundstein für die dynamische Programmierung, eine Methode, die bekanntlich von Richard Bellman selbst begründet wurde und zu weitreichenden Anwendungen in Mathematik, Wirtschaft und Informatik führte.