Bellman-Ford-Algorithmus für kürzeste Wege

Bellman-Ford ist eine passende Wahl, wenn Kantengewichte negativ sein können und du kürzeste Wege ab einer Quelle berechnen möchtest. Dijkstras Greedy-Schritt setzt nichtnegative Gewichte voraus: Sobald ein Knoten als nächster fest gewählt wird, darf später kein negativer Umweg ihn verbessern. Bellman-Ford lockert dagegen wiederholt alle Kanten und lässt solche Verbesserungen zu. Bei ausschließlich nichtnegativen Gewichten ist Dijkstra oft schneller. Beide Algorithmen lösen dasselbe Distanzproblem, aber ihre Voraussetzungen und Laufzeiten unterscheiden sich. Prüfe außerdem, ob ein erreichbarer negativer Kreis existiert. Prüfe zuerst die Eingabegewichte und danach die erreichbaren Zyklen.

Ein negativer Kreis hat entlang seiner gerichteten Kanten eine Summe kleiner als null. Ist er von der Quelle erreichbar und kann danach ein Ziel erreicht werden, kann man den Kreis beliebig oft durchlaufen und den Pfad jedes Mal billiger machen. Dann gibt es für dieses Ziel keinen endlichen kürzesten Weg. Eine einzelne negative Kante verursacht dieses Problem nicht. Bellman-Ford prüft nach den |V|−1 normalen Runden, ob eine weitere Relaxation noch verbessert; so lässt sich ein erreichbarer negativer Kreis erkennen. Nicht erreichbare negative Kreise betreffen die Quelle nicht.

Wenn ein kürzester Weg existiert und kein erreichbarer negativer Kreis vorliegt, kann ein kürzester Weg ohne wiederholten Knoten gewählt werden. Ein solcher einfacher Weg durch höchstens |V| Knoten besitzt höchstens |V|−1 Kanten. In Runde k berücksichtigt die dynamische Programmierung Wege mit höchstens k Kanten. Daher reichen |V|−1 Runden, um jeden einfachen kürzesten Weg abzudecken. In einer Implementierung, die alle Kanten in-place scannt, können Verbesserungen je nach Kantenreihenfolge früher weitergereicht werden; die Schranke bleibt dennoch korrekt. Das ist eine obere Schranke und oft weniger als nötig.

Der einfache Algorithmus führt höchstens |V|−1 Runden aus und prüft in jeder Runde jede der |E| Kanten. Eine Prüfung berechnet d(u)+w(u,v) und vergleicht den Wert mit d(v), also kostet sie konstant viele Rechenschritte. Das ergibt O(|V||E|). Eine zusätzliche Runde zur Negativkreisprüfung ändert die asymptotische Schranke nicht. Wird in einer ganzen Runde kein Abstand verändert, kann man vorzeitig stoppen. Die konkrete Laufzeit kann also besser sein, aber die Standardgarantie für den Kanten-Scan ist das Produkt aus Knotenzahl und Kantenzahl. Dabei zählt eine Kante als eine geprüfte Graphbeziehung.

Vergleiche für eine gerichtete Kante u→v den bisherigen Wert d(v) mit d(u)+w(u,v). Ist die Quelle u noch unerreichbar, also d(u)=∞, entsteht daraus kein endlicher Vorschlag. Im Beispiel kostet s→a vier und a→b minus zwei; dadurch sinkt d(b) von fünf auf zwei. Die Kante b→t mit Gewicht drei setzt d(t) anschließend auf fünf. Der resultierende Weg s→a→b→t hat Kosten 4−2+3=5. Notiere jede Verbesserung und verwende dieselben additiven Gewichtseinheiten. Halte die Kantenrichtung bei jedem Schritt konsequent ein. Prüfe am Ende alle Distanzen nochmals.