Der Bellman–Ford-Algorithmus

Bei manchen Kürzeste-Wege-Problemen gibt es Kanten, die einen Weg billiger machen: eine Rückerstattung, eine Strecke bergab, ein Wechselkurs zu Ihren Gunsten. Der Dijkstra-Algorithmus kommt damit nicht zurecht. Der Bellman–Ford-Algorithmus schon, denn er setzt auf Geduld statt auf Raffinesse.

Ein Graph mit Einbahnpfeilen, einigen negativen Kanten, den bisher gefundenen Abständen auf den Knoten und einem rot gezeichneten negativen Zyklus
Ein Graph mit Einbahnpfeilen, einigen negativen Kanten, den bisher gefundenen Abständen auf den Knoten und einem rot gezeichneten negativen Zyklus

Die Idee

Jeder Kürzeste-Wege-Algorithmus beruht auf einem einzigen Schritt, dem Relaxieren einer Kante: Ist der Weg zu u und dann über die Kante u → v kürzer als der beste bekannte Weg zu v, wird er genommen. Der Dijkstra-Algorithmus relaxiert jede Kante einmal, in einer geschickten Reihenfolge, die nur funktioniert, wenn keine Kante negativ ist. Bellman–Ford setzt das nicht voraus. Er relaxiert jede Kante, in einer beliebigen festen Reihenfolge, immer wieder, bis sich die Abstände nicht mehr ändern.

Schritt für Schritt

Geben Sie dem Start den Abstand 0 und allen anderen Knoten unendlich. Wiederholen Sie bei n Knoten n − 1-mal: Gehen Sie jede Kante u → v durch und relaxieren Sie sie, wenn u einen Abstand hat. Hören Sie früh auf, wenn ein ganzer Durchlauf nichts ändert. Dann folgt noch ein Durchlauf. Lässt sich dabei noch eine Kante relaxieren, ist vom Start aus ein Zyklus mit negativer Summe erreichbar; sonst ist jeder Abstand der kürzeste, und die gemerkten Knoten ergeben die Wege.

Ein Beispiel

Nehmen Sie die Einbahnkanten A → B mit Länge 4, A → C 5, B → D 2 und C → B −3, in dieser Reihenfolge geprüft, mit Start A. Durchlauf 1 gibt B 4, C 5 und D 6, und dann senkt C → B den Abstand von B auf 5 − 3 = 2. Durchlauf 2 senkt D auf 2 + 2 = 4. Durchlauf 3 ändert nichts, also lautet die Antwort B 2, C 5, D 4. Der Dijkstra-Algorithmus hätte B bei 4 und D bei 6 endgültig gemacht, bevor er die negative Kante sieht. Fügen Sie eine Kante D → C mit Länge −4 hinzu, und der Zyklus C → B → D → C hat die Summe −5: Jeder Durchlauf senkt die Abstände erneut, und der Prüfdurchlauf meldet ihn.

Warum n − 1 Durchläufe reichen

Ein kürzester Weg, wenn es einen gibt, wiederholt keinen Knoten, hat also höchstens n − 1 Kanten. Wird in einem Durchlauf jede Kante relaxiert, verlängert das jeden richtig bekannten kürzesten Weg um eine weitere Kante, egal in welcher Reihenfolge die Kanten stehen. Nach Durchlauf k stimmen also alle kürzesten Wege mit bis zu k Kanten, und nach n − 1 Durchläufen alle. Für das Tempo zählt die Reihenfolge trotzdem: Mit einer guten Reihenfolge kann er nach einem oder zwei Durchläufen fertig sein.

Geschichte und Anwendungen

Alfonso Shimbel beschrieb das Verfahren 1955, Lester Ford Jr. 1956, Edward F. Moore 1957 und Richard Bellman 1958; es trägt die Namen von zweien von ihnen, Bellman und Ford. Seine Durchläufe kann jeder Router für sich ausführen, und so wurde es zur Grundlage von Distanzvektor-Routingprotokollen wie RIP. In der Finanzwelt verwandelt der negative Logarithmus von Wechselkursen eine gewinnbringende Runde von Devisengeschäften, eine Arbitrage, in einen negativen Zyklus, den Bellman–Ford finden kann.

Richard Bellman im Jahr 1962, fotografiert von Alfred Eisenstaedt. Er veröffentlichte das Verfahren für kürzeste Wege 1958, nach Shimbel, Ford und Moore.
Richard Bellman im Jahr 1962, fotografiert von Alfred Eisenstaedt. Er veröffentlichte das Verfahren für kürzeste Wege 1958, nach Shimbel, Ford und Moore.

Selbst ausprobieren

Öffnen Sie die App und drücken Sie Schritt. Jede Kante führt nur in eine Richtung, und manche Längen sind negativ. Jeder Schritt prüft eine Kante, in einer festen Reihenfolge, und die Kacheln zeigen den Durchlauf und wie viele Abstände er geändert hat. Meist ändert ein Durchlauf bald nichts mehr, und die Suche hört früh auf. Aktivieren Sie Negativen Zyklus hinzufügen und sehen Sie zu, wie die Abstände Durchlauf für Durchlauf sinken, bis der Prüfdurchlauf den Zyklus findet und rot zeichnet.

Häufig gestellte Fragen

Welche Zeitkomplexität hat Bellman–Ford?

O(V · E) bei V Knoten und E Kanten: bis zu V − 1 Durchläufe, die jeweils jede Kante prüfen. Mit frühem Abbruch ist er in der Praxis oft viel schneller, und im besten Fall reicht ein einziger Durchlauf.

Was ist ein negativer Zyklus?

Ein Zyklus, dessen Kantenlängen zusammen weniger als null ergeben. Wer ihn immer wieder durchläuft, macht einen Weg beliebig kurz, also sind die kürzesten Abstände zu allen Knoten, die über ihn erreichbar sind, nicht definiert.

Funktioniert Bellman–Ford auf ungerichteten Graphen?

Nur wenn keine Kante negativ ist: Eine ungerichtete negative Kante kann hin und zurück durchlaufen werden, und das ist ein negativer Zyklus aus zwei Kanten. Mit nichtnegativen Kanten funktioniert er, aber der Dijkstra-Algorithmus ist schneller.

Was ist SPFA?

Der Shortest Path Faster Algorithm, eine Variante von Bellman–Ford, die mit einer Warteschlange nur die Kanten aus Knoten erneut prüft, deren Abstand sich gerade geändert hat. Er ist oft viel schneller, sein schlechtester Fall ist aber derselbe.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Bellman–Ford ausprobieren