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 Kantenzug 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.

01  für jedes v aus V
02      Distanz(v) := unendlich, Vorgänger(v) := keiner
03  Distanz(s) := 0

04  wiederhole n − 1 mal
05      für jedes (u,v) aus E
06          wenn (Distanz(u) + Gewicht(u,v)) < Distanz(v) dann
07              Distanz(v) := Distanz(u) + Gewicht(u,v)
08              Vorgänger(v) := u

09  für jedes (u,v) aus E
10      wenn (Distanz(u) + Gewicht(u,v)) < Distanz(v) dann
11          STOPP mit Ausgabe „Es gibt einen Zyklus negativen Gewichtes.“

12  Ausgabe Distanz, Vorgänger

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:

Der Graph $G$ aus dem nebenstehenden Codebeispiel

import networkx as nx
G = nx.Graph()
e = [('a', 'b', 3), ('b', 'c', 9), ('a', 'c', 5), ('c', 'd', 12)]
G.add_weighted_edges_from(e)
print(nx.bellman_ford_path(G, 'a', 'd'))
print(nx.bellman_ford_path_length(G, 'a', 'd'))

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.

using System;
using System.Collections.Generic;

// Deklariert die Klasse für die Knoten des Graphen
class Node
{
	public int index;
	public string value;
}

// Deklariert die Klasse für die Kanten des Graphen
class Edge
{
	public Node startNode, targetNode;
	public int weight;
}

// Deklariert die Klasse für den gerichteten Graphen
class DirectedGraph
{
	public HashSet<Node> nodes = new HashSet<Node>();
	public HashSet<Edge> edges = new HashSet<Edge>();
	
	// Diese Methode verbindet die Knoten startNode und targetNode miteinander und weist der Kante ein Gewicht zu.
	public void ConnectNodes(Node startNode, Node targetNode, int weight)
	{
		Edge edge = new Edge();
		edge.startNode = startNode;
		edge.targetNode = targetNode;
		edge.weight = weight;
		edges.Add(edge);
	}
}

class Program
{
	// Diese Methode gibt die kürzesten Abstände vom Knoten mit dem gegebenen Index zurück.
	// Wenn der Graph Zyklen mit negativem Gewicht enthält, gib die Methode den Wert null zurück.
	static int[] BellmanFord(DirectedGraph directedGraph, int index)
	{
		int numberOfNodes = directedGraph.nodes.Count;
		int[] distances = new int[numberOfNodes]; // Array vom Typ int für die kürzesten Abstände
		// Initialisiert das Array mit dem Maximalwert für int
		for (int i = 0; i < numberOfNodes; i++)
		{
			distances[i] = int.MaxValue;
		}
		distances[index] = 0; // Setzt den Abstand des Startknotens von sich selbst auf 0
		
		HashSet<Edge> edges = directedGraph.edges;
		int n = edges.Count; // Anzahl der Kanten
		for (int i = 1; i < n; i++) // for-Schleife mit n - 1 Iterationsschritten, die die Abstände für die Knoten aktualisiert
		{
			foreach (Edge edge in edges) // foreach-Schleife, die alle Kanten durchläuft
			{
				int startIndex = edge.startNode.index;
				int targetIndex = edge.targetNode.index;
				int weight = edge.weight;
				if (distances[startIndex] != int.MaxValue && distances[startIndex] + weight < distances[targetIndex]) // Wenn die Summe der Abstände kleiner als der aktuelle Abstand ist
				{
					distances[targetIndex] = distances[startIndex] + weight; // Aktualisiert den Abstand für den Knoten mit dem Index targetIndex
				}
			}
		}
		// Prüft den Graphen auf Zyklen mit negativem Gewicht
		foreach (Edge edge in edges) // foreach-Schleife, die alle Kanten durchläuft
		{
			int startIndex = edge.startNode.index;
			int targetIndex = edge.targetNode.index;
			int weight = edge.weight;
			if (distances[startIndex] != int.MaxValue && distances[startIndex] + weight < distances[targetIndex]) // Wenn der Graph Zyklen mit negativem Gewicht enthält, wird der Wert null zurückgegeben
			{
				return null;
			}
		}
		return distances; // Sonst wird das Array für die kürzesten Abstände zurückgegeben
	}
	
	// Hauptmethode, die das Programm ausführt
	public static void Main()
	{
		// Deklariert und initialisiert 5 Knoten
		Node node1 = new Node{index = 0, value = "A"};
		Node node2 = new Node{index = 1, value = "B"};
		Node node3 = new Node{index = 2, value = "C"};
		Node node4 = new Node{index = 3, value = "D"};
		Node node5 = new Node{index = 4, value = "E"};
		// Deklariert und initialisiert ein Array mit den Knoten
		Node[] nodes = {node1, node2, node3, node4, node5};
		// Erzeugt einen ungerichteten Graphen
		DirectedGraph directedGraph = new DirectedGraph();
		int numberOfNodes = nodes.Length;
		for (int i = 0; i < numberOfNodes; i++) // for-Schleife, die alle Knoten durchläuft
		{
			directedGraph.nodes.Add(nodes[i]); // Fügt die Knoten dem Graphen hinzu
		}
		// Verbindet Knoten des Graphen miteinander und weist den Kanten Gewichte zu
		directedGraph.ConnectNodes(node1, node2, -1);
		directedGraph.ConnectNodes(node1, node3, 4);
		directedGraph.ConnectNodes(node2, node3, 3);
		directedGraph.ConnectNodes(node2, node4, 2);
		directedGraph.ConnectNodes(node2, node5, 2);
		directedGraph.ConnectNodes(node4, node3, 5);
		directedGraph.ConnectNodes(node4, node2, 1);
		directedGraph.ConnectNodes(node5, node4, -3);
		
		int[] distances = BellmanFord(directedGraph, 0); // Aufruf der Methode
		if (distances != null)
		{
			Console.WriteLine("Abstände der Knoten vom Startknoten"); // Ausgabe auf der Konsole
			for (int i = 0; i < numberOfNodes; i++) // for-Schleife, die alle Knoten durchläuft
			{
				Console.WriteLine(i + "\t\t" + distances[i]); // Ausgabe auf der Konsole
			}
		}
		else // Wenn der Rückgabewert null ist
		{
			Console.WriteLine("Der Graph enthält Zyklen mit negativem Gewicht."); // Ausgabe auf der Konsole
		}
		
		Console.ReadLine();
	}
}

Literatur

• L. R. Ford: Network flow theory, Paper P-923. The Rand Corporation, Santa Monica 1956
• R. E. Bellman: On a Routing Problem. In: Quarterly of Applied Mathematics. 16(1)/1958. Brown University, S. 87–90, ISSN 0033-569X
• E. F. Moore: The shortest path through a maze. In: Proceedings of the International Symposium on the Theory of Switching. 2/1959. Harvard University Press, S. 285–292
• L. R. Ford, D. R. Fulkerson: Flows in Networks. Princeton University Press, Princeton 1962, ISBN 0-691-07962-5
• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. 2. Auflage. Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8, Kapitel 24 und 25. 

Weblinks

• Ein interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus