Bellman-Ford-Algorithmus

Handlungsvorschrift aus der Graphentheorie

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.[1] Der Bellman-Ford-Algorithmus kann das Vorhandensein von Zyklen negativen Gewichtes erkennen.

Beschreibung

Bearbeiten

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

Wenn die Ausführung des Algorithmus endet, kann der Ausgabe entnommen werden, ob   einen Zyklus negativer Länge besitzt. Falls dies nicht der Fall ist, enthält Distanz für jeden Knoten seinen Abstand zu  , also das Gewicht eines von   ausgehenden kürzesten Weges. Durch Vorgänger wird zudem ein Spannbaum definiert, der die von   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   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  -ten Durchlauf der Schleife in Zeile 04 bis 08 wird zu jedem Knoten   ein kürzester Weg vom Startknoten   zum Knoten   mit maximal   Kanten gefunden oder ein kürzerer Weg mit mehr Kanten. Ein Weg ohne Zyklen enthält maximal   Knoten, also   Kanten. Falls in Zeile 10 festgestellt wird, dass ein Weg nicht optimal ist, muss dieser folglich einen Zyklus mit negativem Gewicht enthalten.

Korrektheitsbeweis

Bearbeiten

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

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

  • Wenn   nicht unendlich ist, ist es gleich der Länge eines Pfades von   nach  .
  • Wenn es einen Pfad von   nach   mit höchstens   Kanten gibt, ist   höchstens gleich der Länge des kürzesten Pfades von   nach   mit höchstens   Kanten.

Betrachte für den Induktionsanfang   und den Moment bevor die Schleife zum ersten Mal ausgeführt wird. Dann gilt für den Startknoten  , was korrekt ist. Für andere Knoten   ist  , was ebenfalls korrekt ist, weil es keinen Pfad von   nach   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   aktualisiert wird. Nach Induktionsvoraussetzung ist   die Länge eines Pfades von   nach  . Dann ist   die Länge des Pfades von   nach  , der dem Pfad von   nach   folgt und dann nach   geht.

Betrachte für den zweiten Teil einen kürzesten Pfad   (es kann mehr als einen geben) von   nach   mit höchstens   Kanten. Sei   der letzte Knoten vor   auf diesem Pfad. Dann ist der Teil des Pfades von   nach   ein kürzester Pfad von   nach   mit höchstens   Kanten, denn wenn dies nicht der Fall wäre, müsste es einen kürzeren Pfad von   nach   mit höchstens   Kanten geben, und wir könnten dann die Kante   an diesen Pfad anhängen, um einen Pfad von   nach   mit höchstens   Kanten zu erhalten, der kürzer als   ist - ein Widerspruch. Nach Induktionsvoraussetzung ist   nach   Iterationen höchstens gleich der Länge dieses Pfades von   nach  . Daher ist   höchstens gleich der Länge von  . Im Durchlauf   wird   mit   verglichen und auf diesen Wert gesetzt, wenn   kleiner ist. Daher ist nach   Durchläufen   höchstens gleich der Länge von  , d. h. der Länge des kürzesten Weges von   nach  , der höchstens   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  :

 

Summiert über den Zyklus, dann heben sich die Ausdrücke   und   auf und es ergibt sich:

 

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

Zeitkomplexität

Bearbeiten

Die Laufzeit des Bellman-Ford-Algorithmus ist in  , wobei   die Anzahl der Knoten und   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  -mal. Die Laufzeitkomplexität dafür beträgt folglich  .

Vergleich mit anderen Algorithmen

Bearbeiten

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

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

Bearbeiten

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

Bearbeiten

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

 
Der Graph   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   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.

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.[3]

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

Bearbeiten
  • 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.
Bearbeiten

Einzelnachweise

Bearbeiten
  1. 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, S. 585–586.
  2. Algorithms - Shortest Paths. In: NetworkX 2.2 documentation. Abgerufen am 24. Oktober 2018 (englisch).
  3. GeeksforGeeks: Bellman–Ford Algorithm