Bellman-Ford-Algorithmus
# Bellman-Ford-Algorithmus

Der Algorithmus von Bellman und Ford (nach seinen Erfindern Richard Bellman und Lester Ford) ist ein Algorithmus der Graphentheorie und dient der Berechnung der kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen. Gelegentlich wird auch vom Moore-Bellman-Ford-Algorithmus gesprochen, da auch Edward F. Moore zu seiner Entwicklung beigetragen hat.

Anders als beim Algorithmus von Dijkstra, dem bekanntesten Verfahren zur Suche nach kürzesten Wegen in Graphen, dürfen hier die Gewichte der Kanten auch negativ sein. Zyklen negativen Gewichtes, die vom Startknoten aus erreichbar sind, müssen jedoch ausgeschlossen werden, denn andernfalls könnten diese beliebig oft durchlaufen und somit Wege immer geringeren Gewichts konstruiert werden, es gäbe also überhaupt keinen Weg geringsten Gewichts. Der Bellman-Ford-Algorithmus kann das Vorhandensein von Zyklen negativen Gewichtes erkennen.

## Beschreibung

$G$ bezeichnet den gewichteten Graphen mit der Knotenmenge $V$ und der Kantenmenge $E$. Gewicht gibt das Gewicht einer Kante zwischen zwei Knoten an. $s$ ist der Startknoten, von dem ausgehend die kürzesten Wege zu allen anderen Knoten berechnet werden, und $n$ ist die Anzahl der Knoten in $V$.

Wenn die Ausführung des Algorithmus endet, kann der Ausgabe entnommen werden, ob $G$ einen Zyklus negativer Länge besitzt. Falls dies nicht der Fall ist, enthält Distanz für jeden Knoten seinen Abstand zu $s$, also das Gewicht eines von $s$ ausgehenden kürzesten Weges. Durch Vorgänger wird zudem ein Spannbaum definiert, der die von $s$ ausgehenden kürzesten Wege in Form eines In-Trees speichert. Ausgehend von einem Knoten kann man darin den entsprechenden kürzesten Weg rückwärts ermitteln, indem man rekursiv so lange den Knoten besucht, der durch Vorgänger gegeben ist, bis man $s$ erreicht hat.

Im $k$-ten Durchlauf der Schleife in Zeile 04 bis 08 wird zu jedem Knoten $v$ ein kürzester Weg vom Startknoten $s$ zum Knoten $v$ mit maximal $k$ Kanten gefunden oder ein kürzerer Weg mit mehr Kanten. Ein Weg ohne Zyklen enthält maximal $n$ Knoten, also $n-1$ Kanten. Falls in Zeile 10 festgestellt wird, dass ein Weg nicht optimal ist, muss dieser folglich einen Zyklus mit negativem Gewicht enthalten.

## Korrektheitsbeweis

Die Richtigkeit des Algorithmus kann durch vollständige Induktion gezeigt werden.

Nach $i$ Durchläufen der Schleife in Zeile 04 bis 08 gilt:

* Wenn $\mathrm {Distanz} (u)$ nicht unendlich ist, ist es gleich der Länge eines Pfades von $s$ nach $u$.
* Wenn es einen Pfad von $s$ nach $u$ mit höchstens $i$ Kanten gibt, ist $\mathrm {Distanz} (u)$ höchstens gleich der Länge des kürzesten Pfades von $s$ nach $u$ mit höchstens $i$ Kanten.

Betrachte für den Induktionsanfang $i=0$ und den Moment bevor die Schleife zum ersten Mal ausgeführt wird. Dann gilt für den Startknoten $\mathrm {Distanz} (s)=0$, was korrekt ist. Für andere Knoten $v$ ist $\mathrm {Distanz} (v)=\infty$, was ebenfalls korrekt ist, weil es keinen Pfad von $s$ nach $v$ mit 0 Kanten gibt.

Für den induktiven Fall beweisen wir zunächst den ersten Teil. Betrachte den Schritt, in dem die Entfernung eines Knotens durch $\mathrm {Distanz} (v):=\mathrm {Distanz} (u)+\mathrm {Gewicht} (u,v)$ aktualisiert wird. Nach Induktionsvoraussetzung ist $\mathrm {Distanz} (u)$ die Länge eines Pfades von $s$ nach $u$. Dann ist $\mathrm {Distanz} (u)+\mathrm {Gewicht} (u,v)$ die Länge des Pfades von $s$ nach $v$, der dem Pfad von $s$ nach $u$ folgt und dann nach $v$ geht.

Betrachte für den zweiten Teil einen kürzesten Pfad $P$ (es kann mehr als einen geben) von $s$ nach $v$ mit höchstens $i$ Kanten. Sei $u$ der letzte Knoten vor $v$ auf diesem Pfad. Dann ist der Teil des Pfades von $s$ nach $u$ ein kürzester Pfad von $s$ nach $u$ mit höchstens $i-1$ Kanten, denn wenn dies nicht der Fall wäre, müsste es einen kürzeren Pfad von $s$ nach $u$ mit höchstens $i-1$ Kanten geben, und wir könnten dann die Kante $(u,v)$ an diesen Pfad anhängen, um einen Pfad von $s$ nach $v$ mit höchstens $i$ Kanten zu erhalten, der kürzer als $P$ ist - ein Widerspruch. Nach Induktionsvoraussetzung ist $\mathrm {Distanz} (u)$ nach $i-1$ Iterationen höchstens gleich der Länge dieses Pfades von $s$ nach $u$. Daher ist $\mathrm {Distanz} (u)+\mathrm {Gewicht} (u,v)$ höchstens gleich der Länge von $P$. Im Durchlauf $i$ wird $\mathrm {Distanz} (v)$ mit $\mathrm {Distanz} (u)+\mathrm {Gewicht} (u,v)$ verglichen und auf diesen Wert gesetzt, wenn $\mathrm {Distanz} (u)+\mathrm {Gewicht} (u,v)$ kleiner ist. Daher ist nach $i$ Durchläufen $\mathrm {Distanz} (v)$ höchstens gleich der Länge von $P$, d. h. der Länge des kürzesten Weges von $s$ nach $v$, der höchstens $i$ Kanten enthält.

Wenn es keine Zyklen mit negativem Gewicht gibt, enthält jeder kürzeste Pfad jeden Knoten höchstens einmal, sodass in Zeile 09 bis 11 keine weiteren Verbesserungen gemacht werden können. Nehmen wir umgekehrt an, dass keine Verbesserung gemacht werden kann. Dann gilt für jeden Zyklus mit den Knoten $v_{0},\ldots ,v_{k-1}$:

    $\mathrm {Distanz} (v_{i})\leq \mathrm {Distanz} (v_{(i-1\mod k)})+\mathrm {Gewicht} (v_{(i-1\mod k)},v_{i})$

Summiert über den Zyklus, dann heben sich die Ausdrücke $\mathrm {Distanz} (v_{i})$ und $\mathrm {Distanz} (v_{(i-1\mod k)})$ auf und es ergibt sich:

    $0\leq \sum _{i=1}^{k}\mathrm {Gewicht} (v_{(i-1\mod k)},v_{i})$

Das heißt, jeder Zyklus hat ein nichtnegatives Gewicht.

## Zeitkomplexität

Die Laufzeit des Bellman-Ford-Algorithmus ist in ${\mathcal {O}}(n\cdot m)$, wobei $n$ die Anzahl der Knoten und $m$ die Anzahl der Kanten im Graphen sind.

Will man die kürzesten Wege von jedem Knoten zu jedem anderen Knoten finden, so muss man den Algorithmus für jeden Startknoten einmal anwenden, insgesamt also $n$-mal. Die Laufzeitkomplexität dafür beträgt folglich ${\mathcal {O}}(n^{2}\cdot m)$.

## Vergleich mit anderen Algorithmen

Schneller als der Bellman-Ford-Algorithmus ist der Dijkstra-Algorithmus, ein Greedy-Algorithmus zur Suche kürzester Wege, der sukzessive den jeweils nächstbesten Knoten aus einer Priority Queue in eine Ergebnismenge S aufnimmt. Er hat eine Laufzeit von ${\mathcal {O}}(n\cdot \log(n)+m)$. Sein Nachteil besteht jedoch darin, dass er als Eingabe nur Graphen mit nichtnegativen Gewichten zulässt.

Der A*-Algorithmus erweitert den Dijkstra-Algorithmus um eine Abschätzfunktion und hat die Laufzeit ${\mathcal {O}}(n^{2})$.

Ein anderes Verfahren zur Suche kürzester Wege, das wie der Bellman-Ford-Algorithmus auf Dynamischer Programmierung beruht, ist der Floyd-Warshall-Algorithmus. Beide stützen ihre Korrektheit auf das Optimalitätsprinzip von Bellman.

## Anwendungen

Der Bellman-Ford-Algorithmus findet unter anderem im Distanzvektoralgorithmus, einem dynamischen Routing-Algorithmus, Verwendung. Dieser wird z. B. vom Routing Information Protocol eingesetzt, mit dem Routingtabellen innerhalb einer administrativen Netzwerk-Domain dynamisch erstellt werden (Interior Gateway Protocol).

Eine verteilte Variante des Bellman-Ford-Algorithmus wird in Distanzvektor-Routing-Protokollen verwendet, beispielsweise das Routing Information Protocol. Der Algorithmus ist verteilt, da er eine Anzahl von Knoten (Routern) innerhalb eines autonomen Systems umfasst, einer Sammlung von IP-Netzwerken, die normalerweise einem Internet Service Provider gehören. Es besteht aus folgenden Schritten:

* Jeder Knoten berechnet die Abstände zwischen sich und allen anderen Knoten innerhalb des autonomen Systems und speichert diese Informationen als Tabelle.
* Jeder Knoten sendet seine Tabelle an alle benachbarten Knoten.
* Wenn ein Knoten Entfernungstabellen von seinen Nachbarn empfängt, berechnet er die kürzesten Wege zu allen anderen Knoten und aktualisiert seine eigene Tabelle, um etwaige Änderungen wiederzugeben.

Die Hauptnachteile des Bellman-Ford-Algorithmus in diesem Umfeld sind folgende:

* Er skaliert nicht gut.
* Änderungen in der Netzwerktopologie werden nicht schnell wiedergegeben, da Aktualisierungen Knoten für Knoten verteilt werden.
* Er zählt bis unendlich, wenn Verbindungs- oder Knotenfehler einen Knoten von einer Reihe anderer Knoten aus nicht erreichbar machen. Diese Knoten verbringen möglicherweise ewig damit, ihre Schätzungen der Abstände zu ihm schrittweise zu erhöhen, und in der Zwischenzeit kann es zu Routing-Schleifen kommen.

## Programmierung

### Python

Der Algorithmus ist in der freien Python-Bibliothek NetworkX implementiert. Beispiel:

Im obigen Beispiel wird ein Graph $G$ mit den Knoten a, b, c und d definiert. Zwischen den Knoten a-b, b-c, a-c und c-d existieren Kanten mit den Gewichten ("weight") 3, 9, 5 und 12. Es wird sodann auf dem Graph der Bellman-Ford-Algorithmus ausgeführt, um zwischen den Knoten a und d die kürzeste Strecke aufzufinden. Das Ergebnis ist folglich die Strecke a-c-d. Danach wird die minimale Länge zwischen den Knoten a und d berechnet, was als Ergebnis 5 + 12 = 17 ergibt.

### C#

Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung eines gerichteten Graphen. Der gerichtete Graph wird als Klasse DirectedGraph deklariert. Bei der Ausführung des Programms wird die Methode Main verwendet, die – falls der Graph keine Zyklen mit negativem Gewicht enthält – die kürzesten Abstände vom Startknoten auf der Konsole ausgibt.

