Bellman-Ford-Algorithmus - LinkFang.de





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

Algorithmus

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

Im [math]k[/math]-ten Schleifendurchlauf (04 – 08) wird zu jedem Knoten [math]x[/math] ein kürzester [math]s[/math]-[math]x[/math]-Weg mit maximal [math]k[/math] Kanten gefunden oder ein kürzerer Weg mit mehr Kanten. Ein Weg ohne Zyklen enthält maximal [math]n[/math] Knoten, also [math]n - 1[/math] Kanten. Falls in (09 – 11) festgestellt wird, dass ein Weg nicht optimal ist, muss dieser folglich einen Zyklus mit negativem Gewicht enthalten.

Komplexität

Die Laufzeit des Algorithmus ist in [math] \mathcal{O} \left( n \cdot m \right) [/math], wobei [math]n[/math] die Anzahl der Knoten und [math]m[/math] 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 [math] \mathcal{O} \left( n^2 \cdot m \right) [/math].

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 Netzwerkdomain dynamisch erstellt werden (Interior Gateway Protocol).

Andere Verfahren zur Berechnung kürzester Wege

Schneller als der Bellman-Ford-Algorithmus ist der Algorithmus von Dijkstra, ein Greedy-Algorithmus zur Suche kürzester Wege, der sukzessive den jeweils nächstbesten Knoten aus einer Priority Queue in eine Ergebnismenge S aufnimmt. Sein Nachteil besteht jedoch darin, dass er als Eingabe nur Graphen mit nichtnegativen Gewichten zulässt. Der A*-Algorithmus erweitert den Algorithmus von Dijkstra um eine Abschätzfunktion. 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.

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

Einzelnachweise

  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.

Kategorien: Graphsuchalgorithmus | Reise- und Routenplanung

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.