Bellman-Ford Rechner

Pseudocode

Bellman-Ford ist der Kürzeste-Wege-Algorithmus, der Raffinesse gegen Allgemeinheit eintauscht. Es gibt keine Prioritätswarteschlange und keine Reihenfolgeentscheidung, nur wiederholtes Relaxieren aller Kanten.

BellmanFord(graph, quelle):
    für jeden Knoten v: dist[v] = unendlich
    dist[quelle] = 0

    wiederhole V - 1 mal:
        geändert = falsch
        für jede Kante (u, v, w):
            wenn dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                vorgänger[v] = u
                geändert = wahr
        wenn nicht geändert: abbrechen   // frühzeitig

    // Ein zusätzlicher Durchlauf erkennt negative Zyklen
    für jede Kante (u, v, w):
        wenn dist[u] + w < dist[v]:
            melde erreichbaren negativen Zyklus

Die Invariante lautet: Nach Durchlauf i ist jeder kürzeste Weg mit höchstens i Kanten korrekt. Da ein kürzester Weg in einem Graphen ohne negative Zyklen höchstens V - 1 Kanten benutzt, klären V - 1 Durchläufe alles. Verbessert ein V-ter Durchlauf noch etwas, wird ein Weg unbegrenzt kürzer, und genau das bedeutet ein negativer Zyklus.

Durchgerechnetes Beispiel, Schritt für Schritt

Führe Bellman-Ford von A aus auf einem Graphen mit einer negativen Kante, die Dijkstra falsch behandeln würde. Die Kanten werden in der angegebenen festen Reihenfolge relaxiert.

Beispielgraph: Gerichtete Kanten A nach B (4), A nach C (5), B nach C (-3) und C nach D (2).

1. Initialisieren. dist = A 0, B unendlich, C unendlich, D unendlich.
2. Durchlauf 1. A nach B setzt dist[B] = 4. A nach C setzt dist[C] = 5. B nach C bietet 4 + (-3) = 1, besser als 5, also dist[C] = 1. C nach D setzt dist[D] = 1 + 2 = 3. Nach einem Durchlauf: A 0, B 4, C 1, D 3.
3. Durchlauf 2. Alle Kanten werden erneut geprüft und nichts verbessert sich. Mit der Prüfung auf frühzeitigen Abbruch endet der Algorithmus hier, statt die übrigen Durchläufe auszuführen.
4. Prüfung auf negative Zyklen. Ein weiterer Durchlauf über alle vier Kanten findet keine Verbesserung mehr, also gibt es keinen von A erreichbaren negativen Zyklus und die Distanzen sind endgültig.
5. Warum Dijkstra hier scheitert. Dijkstra würde C bei Distanz 5 endgültig festlegen, sobald C die Prioritätswarteschlange verlässt, weil er annimmt, ein festgelegter Knoten könne sich nicht mehr verbessern. Die spätere Kante B nach C mit Gewicht -3 bliebe dann unbeachtet, und Dijkstra meldete dist[C] = 5 und dist[D] = 7 statt der korrekten 1 und 3.

Die korrekten Distanzen sind A 0, B 4, C 1, D 3. Eine einzige negative Kante genügt, um Dijkstra zu brechen, und das ist der Grund, warum es Bellman-Ford gibt.

Komplexität und woher sie kommt

Zeit: O(VE) · Speicher: O(V)

Der Algorithmus führt V - 1 Durchläufe aus, und jeder Durchlauf relaxiert alle E Kanten einmal, was O(VE) ergibt. Der Speicher besteht aus je einem Distanz- und einem Vorgängereintrag pro Knoten, also O(V) und bemerkenswerterweise unabhängig von E. Bei einem dichten Graphen, in dem E sich V hoch 2 nähert, nähert sich die Laufzeit O(V hoch 3), weshalb Bellman-Ford Fällen vorbehalten bleibt, in denen tatsächlich negative Gewichte auftreten. Die Prüfung auf frühzeitigen Abbruch, die stoppt, sobald ein Durchlauf nichts mehr ändert, endet bei realen Graphen oft nach wenigen Durchläufen, auch wenn der schlechteste Fall bei V - 1 bleibt.

Wann Bellman-Ford-Algorithmus passt und wann nicht

Bellman-Ford ist strikt allgemeiner als Dijkstra und strikt langsamer. Wähle ihn nur, wenn du wirklich brauchst, was er bietet.

Häufige Fehler

• Nur V - 1 Durchläufe ausführen und aufhören. Ohne den zusätzlichen V-ten Durchlauf lassen sich korrekte Distanzen nicht von Distanzen unterscheiden, die noch durch einen negativen Zyklus fallen. Der Erkennungsdurchlauf ist keine optionale Buchführung, sondern das, was die Ausgabe vertrauenswürdig macht.
• Annehmen, ein gemeldeter negativer Zyklus betreffe den ganzen Graphen. Der zusätzliche Durchlauf erkennt nur Zyklen, die von der Quelle erreichbar sind. Ein negativer Zyklus in einer unerreichbaren Komponente bleibt unsichtbar und ist für die Einzelquellenfrage auch irrelevant. Brauchst du alle negativen Zyklen, starte von einer virtuellen Quelle, die mit jedem Knoten verbunden ist.
• Von Knoten mit unendlicher Distanz relaxieren. In Sprachen, in denen unendlich eine große ganze Zahl statt eines Gleitkommawerts ist, läuft dist[u] + w über und wird negativ, was Scheinverbesserungen erzeugt. Sichere die Relaxation mit einer Prüfung ab, dass dist[u] nicht mehr unendlich ist.
• Ihn aus Vorsicht auf nichtnegativen Graphen einsetzen. Auf einem Graphen ohne negative Kanten berechnet Bellman-Ford genau dasselbe wie Dijkstra, kann aber um Größenordnungen langsamer sein. Allgemeinheit ist nicht kostenlos.
• Bei einem negativen Zyklus überhaupt kürzeste Wege erwarten. Ist ein negativer Zyklus erreichbar, existiert kein kürzester Weg, er ist nicht bloß unbekannt: Man kann den Zyklus stets erneut durchlaufen und tiefer kommen. Melde den Zyklus, statt eine Distanz zurückzugeben.

Häufig gestellte Fragen

Wofür wird der Bellman-Ford-Algorithmus verwendet?

Er berechnet kürzeste Wege von einer einzelnen Quelle in Graphen, die negative Kantengewichte enthalten dürfen, und erkennt negative Zyklen. In der Praxis trägt er Distanzvektor-Routingprotokolle wie RIP, die Erkennung von Währungsarbitrage, bei der Wechselkurse zu negativen Logarithmen werden, und Planungsprobleme, in denen manche Übergänge einen Gewinn statt Kosten bedeuten.

Warum Bellman-Ford statt Dijkstra verwenden?

Weil Dijkstra bei negativen Kanten falsch ist. Dijkstra legt einen Knoten endgültig fest, sobald er die Prioritätswarteschlange verlässt, in der Annahme, nichts könne ihn später verbessern, und eine danach entdeckte negative Kante bricht diese Annahme. Bellman-Ford geht keine solche Festlegung ein und bleibt daher korrekt, zum Preis von O(VE) statt O((V + E) log V).

Wie erkennt Bellman-Ford negative Zyklen?

Nach V - 1 Relaxationsdurchläufen ist jeder mögliche kürzeste Weg bereits endgültig, denn ein einfacher Weg hat höchstens V - 1 Kanten. Verbessert ein weiterer Durchlauf über alle Kanten noch eine Distanz, kann diese Verbesserung nur aus einem von der Quelle erreichbaren Zyklus mit negativem Gesamtgewicht stammen.

Wie ist die Zeitkomplexität von Bellman-Ford?

O(VE) Zeit und O(V) Speicher. Er führt V - 1 Durchläufe über alle E Kanten aus. Mit der Optimierung für frühzeitigen Abbruch endet er bei realen Graphen oft weit früher, der schlechteste Fall bleibt jedoch gleich. Bei dichten Graphen nähert sich das O(V hoch 3).

Kann Bellman-Ford negative Gewichte verarbeiten?

Ja, das ist sein ganzer Zweck, sofern kein negativer Zyklus von der Quelle erreichbar ist. Mit negativen Gewichten, aber ohne negativen Zyklus liefert er korrekte kürzeste Wege. Mit einem erreichbaren negativen Zyklus existiert kein kürzester Weg, und der Algorithmus meldet das, statt eine sinnlose Distanz zurückzugeben.