Wie komme ich am günstigsten von links nach rechts?

Was möchtest du zuerst tun?

Eingabe: Gewichteter, ungerichteter Graph G=(V,E) mit Gewichtsfunktion l.
Ausgabe: Eine Liste {d(v[j]) : j = 1,..,n}, die die Distanzen dist(v[1],v[j]) = d(v[j]) enthält,
         falls von v[1] aus keine Kreise negativer Länge erreichbar sind.
         Die Meldung "Kreis negativer Länge", falls von v[1] ein solcher Kreis erreichbar ist.

BEGIN
   d(v[1]) ← 0
   FOR j = 2,..,n DO
      d(v[j]) ← ∞
   FOR i = 1,..,(|V|-1) DO
      FOR ALL (u,v) aus E DO
         d(v) ← min(d(v), d(u) + l(u,v))
   FOR ALL (u,v) aus E DO
      IF d(v) > d(u) + l(u,v) DO
         Meldung: "Kreis negativer Länge"
END

Geschwindigkeit von Algorithmen

Die Geschwindigkeit von Algorithmen wird üblicherweise in der Anzahl an Einzelschritten gemessen, die der Algorithmus bei der Ausführung benötigt.

Einzelschritte sind beispielsweise:

• Zuweisungen – Weise Knoten 1 den Wert 20 zu.
• Vergleiche – Ist 20 größer als 23?
• Vergleich und Zuweisung – Falls 20 größer als 15 ist, setze Variable n auf 20.
• Einfache Arithmetische Operationen – Was ist 5 + 5 ?

Da es sehr schwierig sein kann, diese Einzelschritte exakt zu zählen, möchte man nur die ungefähre Größenordnung der Anzahl Schritte wissen. Man spricht auch von der Laufzeit des Algorithmus. Meistens ist es besonders interessant, zu wissen, wie die Geschwindigkeit des Algorithmus von der Größe der Eingabe (hier: Anzahl Kanten und Knoten im Graph) abhängt.

Laufzeit des Bellman-Ford-Algorithmus

Nehmen wir an, dass der Bellman-Ford-Algorithmus auf einem Graph mit n Knoten und m Kanten ausgeführt wird.

Am Anfang wird jedem Knoten der Wert ∞ zugewiesen. Dafür benötigen wir n Einzelschritte.

Danach kommen die n-1 Phasen des Algorithmus – eine Phase weniger als es Knoten gibt. In jeder Phase wird jede Kante des Graphen überprüft, und möglicherweise wird der Abstandswert ihres Zielknotens verändert. Wir können diese Überprüfung und Zuweisung als einen Schritt sehen und haben also in jeder Phase m Einzelschritte. Insgesamt benötigen die Phasen also m · (n-1) Einzelschritte.

Schließlich überprüft der Algorithmus noch, ob es negative Kreise gibt. Dafür betrachtet er jede Kante einmal. Insgesamt braucht er für die Überprüfung also m Einzelschritte.

Die Gesamtlaufzeit des Algorithmus ist von der Größenordnung m · n Schritte, weil die n Schritte zu Beginn und die m Schritt am Schluss des Algorithmus vernachlässigbar gegenüber m · (n-1) sind.

Ein mathematischer Beweis

In diesem Abschnitt werden wir beweisen, dass der Bellman-Ford-Algorithmus immer ein korrektes Ergebnis liefert, falls der Graph keine vom Startknoten erreichbaren negativen Kreise hat.

Das Prinzip der Induktion

Der Beweis basiert auf dem Prinzip der Induktion. Wir beweisen zunächst, dass wir zu Beginn der ersten Phase bereits die Kosten für mindestens einen Knoten korrekt berechnet haben. Wir zeigen dann, dass wir in jeder Phase die bisherigen Schätzungen verbessern. Am Ende jeder Phase kennen wir also für mehr Knoten die korrekten Kosten als zu Beginn der Phase. Außerdem zerstören wir in der jeweiligen Phase keine Informationen – die Schätzungen können nur besser werden.

Schließlich zeigen wir, dass uns weniger Phasen reichen, als es Knoten gibt, um für alle Knoten die korrekten Kosten zu berechnen.

Nach Phase i gilt:

Der Algorithmus hat jedem Knoten u als Kostenschätzung höchstens die Länge des kürzesten Weges vom Startknoten zu u, der maximal i Kanten benutzt, zugewiesen, falls ein solcher Weg existiert.

Betrachten wir diese Aussage in ihren Einzelteilen für einen Knoten u am Ende von Phase i:

Falls kein Weg vom Startknoten zu u existiert, der maximal i Kanten benutzt, so erfahren wir nichts.

Falls ein Weg vom Startknoten zu u existiert, der maximal i Kanten benutzt, dann wissen wir, dass die Kostenschätzung für u höchstens so hoch ist wie die Kosten des Weges. Der Grund ist folgender: Wenn wir den Weg ohne seine letzte Kante betrachten, so sehen wir einen Weg, der i-1 Kanten benutzt. Die Kosten des letzten Knotens dieses Weges hatten wir also schon zu Beginn der Phase korrekt berechnet. Innerhalb der Phase haben wir alle Kanten, also auch das letzte Teilstück, betrachtet. Da wir beim Betrachten des letzten Teilstücks die Kosten korrekt aktualisiert haben, sind jetzt auch die Kosten für den letzten Knoten des Gesamtwegs, der i Kanten benutzt, korrekt.

Es reichen weniger Phasen, als es Knoten gibt.

Ein Weg, der mindestens so viele Kanten benutzt, wie es Knoten gibt, kann kein kürzester Weg sein, falls alle Kreise positives Gesamtgewicht haben. Mit jeder Kante, die ein Weg benutzt, sieht er nämlich einen weiteren Knoten (den Zielknoten der Kante). Dazu kommt noch der Startknoten, den er auch sieht, ohne Kanten benutzt zu haben. Falls er also so viele Kanten benutzt, wie es Knoten gibt, so hat er mindestens einen Knoten zweimal gesehen, ist also im Kreis gelaufen. Da wir angenommen haben, dass alle Kreise positives Gesamtgewicht haben, wäre es kürzer gewesen, nicht im Kreis zu laufen.

Falls es Kreise mit Gesamtgewicht 0 gibt, so ist es schlicht genauso teuer, diese zu durchlaufen, wie sie auszulassen. Auch in diesem Fall reichen also die Wege, die weniger Kanten benutzen, als es Knoten gibt.

Weitere Graphalgorithmen werden auf der Webseite des Lehrstuhls M9 der TU München erklärt.

Außerdem gibt es ein interessantes Buch zu kürzesten Wegen: Das Geheimnis des kürzesten Weges

Ein Mathematikstudium an der TU München beantwortet alle Fragen zur Graphentheorie (falls eine Lösung bekannt ist).

Der Lehrstuhl M9 der TU München beschäftigt sich mit diskreter Mathematik, angewandter Geometrie und der mathematischen Optimierung von angewandten Problemen. Die hier dargestellten Algorithmen sind sehr grundlegende Beispiele für Verfahren der diskreten Mathematik (die tägliche Forschung des Lehrstuhls geht weit darüber hinaus). Die vorliegenden Seiten sollen SchülerInnen und Studierenden dabei helfen, diese auch im realen Leben sehr wichtigen Verfahren (besser) zu verstehen und durch Ausprobieren zu durchdringen. Aus diesem Grund konzentriert sich die Darstellung bewusst auf die Ideen der Algorithmen, und präsentiert diese oftmals unter weitestgehendem Verzicht auf mathematische Notation.

Bitte beachten Sie, dass diese Seiten im Rahmen von studentischen Arbeiten unter Betreuung des Lehrstuhls M9 erstellt wurden. Den dabei entstandenen Code und die zugehörige Darstellung können wir nur punktuell überprüfen, und können deshalb keine Garantie für die vollständige Korrektheit der Seiten und der implementierten Algorithmen übernehmen.

Selbstverständlich freuen wir uns über jegliches (auch kritisches) Feedback bezüglich der Anwendungen sowie eventuellen Ungenauigkeiten und Fehlern der Darstellung und der Algorithmen. Bitte nutzen Sie hierzu den Anregungen-Link, welcher auch rechts in der Fußleiste zu finden ist.

Um diese Seite zu zitieren, nutze bitte die folgenden Angaben:

• Titel: Der Bellman-Ford - Algorithmus
• Autoren: Melanie Herzog, Wolfgang F. Riedl, Richard Stotz; Technische Universität München
• Link: https://www-m9.ma.tum.de/graph-algorithms/spp-bellman-ford