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.[1] Der Bellman-Ford-Algorithmus kann das Vorhandensein von Zyklen negativen Gewichtes erkennen.
Beschreibung
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
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
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
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
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.[2] Beispiel:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Simple_graph_example_for_illustration_of_Bellman-Ford_algorithm.svg/220px-Simple_graph_example_for_illustration_of_Bellman-Ford_algorithm.svg.png)
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.
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.[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
- 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
Einzelnachweise
- ↑ 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.
- ↑ Algorithms - Shortest Paths. In: NetworkX 2.2 documentation. Abgerufen am 24. Oktober 2018 (englisch).
- ↑ GeeksforGeeks: Bellman–Ford Algorithm