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. Kreise 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 Kreisen negativen Gewichtes erkennen.

Inhaltsverzeichnis

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 Kreis 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)
07          dann
08              Distanz(v) := Distanz(u) + Gewicht(u,v)
09              Vorgänger(v) := u

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

13  Ausgabe Distanz

Im k-ten Schleifendurchlauf (04 – 09) wird zu jedem Knoten x ein kürzester s-x-Weg mit maximal k Kanten gefunden oder ein kürzerer Weg mit mehr Kanten. Ein Weg ohne Kreise enthält maximal n Knoten, also n − 1 Kanten. Falls in (10 – 12) festgestellt wird, dass ein Weg nicht optimal ist, muss dieser folglich einen Kreis mit negativem Gewicht enthalten.

Komplexität

Die Laufzeit des Algorithmus ist in  \mathcal{O} \left( n \cdot m \right) , wobei n die Anzahl der Knoten und m die Anzahl der Kanten im Graphen sind. Wendet man den Algorithmus an, um kürzeste Wege von jedem Knoten zu jedem anderen Knoten zu finden, so beträgt die Komplexität  \mathcal{O} \left( n^2  \cdot m \right) .

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.

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.

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


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Moore-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.… …   Deutsch Wikipedia

  • Bellman-Ford-Moore-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.… …   Deutsch Wikipedia

  • Algorithmus von Bellman und Ford — 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.… …   Deutsch Wikipedia

  • Algorithmus von Dijkstra — Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ… …   Deutsch Wikipedia

  • Algorithmus von Floyd und Warshall — Der Algorithmus von Floyd und Warshall (auch Floyd Warshall Algorithmus oder Tripel Algorithmus), benannt nach Robert Floyd und Stephen Warshall, ist ein Algorithmus der Graphentheorie. In Floyds Version findet er die kürzesten Pfade zwischen… …   Deutsch Wikipedia

  • Bellmann-Ford — 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.… …   Deutsch Wikipedia

  • Dijkstras Algorithmus — Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ… …   Deutsch Wikipedia

  • Floyd-Warshall-Algorithmus — Der Algorithmus von Floyd und Warshall (auch Floyd Warshall Algorithmus oder Tripel Algorithmus), benannt nach Robert Floyd und Stephen Warshall, ist ein Algorithmus der Graphentheorie. Er findet die Länge der kürzesten Wege zwischen allen Paaren …   Deutsch Wikipedia

  • Floyd Warshall Algorithmus — Der Algorithmus von Floyd und Warshall (auch Floyd Warshall Algorithmus oder Tripel Algorithmus), benannt nach Robert Floyd und Stephen Warshall, ist ein Algorithmus der Graphentheorie. Er findet die Länge der kürzesten Wege zwischen allen Paaren …   Deutsch Wikipedia

  • Tripel-Algorithmus — Der Algorithmus von Floyd und Warshall (auch Floyd Warshall Algorithmus oder Tripel Algorithmus), benannt nach Robert Floyd und Stephen Warshall, ist ein Algorithmus der Graphentheorie. Er findet die Länge der kürzesten Wege zwischen allen Paaren …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”