Bellman-Ford-Algorithmus
- Eingeführt von
- Richard Bellman and Lester R. Ford
- Jahr
- 1956
- Typ
- algorithm
- Familie
- Graph Algorithms
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Der Bellman-Ford-Algorithmus, entwickelt von Richard Bellman und Lester R. Ford in den 1950er Jahren, ist ein fundamentaler Algorithmus zur Berechnung von kürzesten Pfaden in gewichteten Graphen, die negative Kantengewichte enthalten können.
Im Gegensatz zu Dijkstras Algorithmus behandelt er negative Gewichte korrekt und kann das Vorhandensein von Zyklen negativen Gewichts erkennen.
Die Intuition hinter der Methode
Der Algorithmus funktioniert durch iteratives Relaxieren von Kanten: Für jede Kante wird geprüft, ob der Weg über diese Kante zu einem kürzeren Pfad zum Ziel führt als der aktuell beste bekannte Pfad. Durch Wiederholung dieses Prozesses für alle Kanten V-1 Mal, wobei V die Anzahl der Knoten ist, garantiert der Algorithmus das Finden des kürzesten Pfades auch bei negativen Gewichten. Die zentrale Erkenntnis ist, dass jeder kürzeste Pfad in einem Graphen mit V Knoten höchstens V-1 Kanten enthält; wenn sich die Distanzen nach V-1 Iterationen immer noch verbessern, muss ein negativer Zyklus existieren.
Geschichte
Richard Bellman entwickelte den Algorithmus 1958 unter Verwendung von Prinzipien der dynamischen Programmierung, während Lester R. Ford 1956 unabhängig einen ähnlichen Ansatz für Netzwerkflüsse entdeckte. Der Algorithmus wurde in den 1960er Jahren weiterentwickelt und verbessert, mit Anwendungen, die sich auf Netzwerk-Routing und ökonomische Anwendungen erstreckten. Moderne Varianten umfassen den Shortest Path Faster Algorithm (SPFA) und verschiedene Optimierungen für spezifische Graphstrukturen, obwohl der grundlegende Bellman-Ford-Ansatz eine klassische Referenz im Algorithmenentwurf bleibt.
Wann wird sie eingesetzt?
Wenden Sie den Bellman-Ford-Algorithmus an, wenn kürzeste Pfade in Graphen mit negativen Kantengewichten berechnet werden. Er ist unerlässlich für die Erkennung von Währungsarbitrage, für Netzwerkprotokolle, bei denen Gewichte negativ sein können, und für jede Anwendung, bei der negative Kosten oder Gewichte eine Rolle spielen. Verwenden Sie Dijkstras Algorithmus, wenn alle Gewichte nicht-negativ sind, da er effizienter ist. Zur Erkennung negativer Zyklen ohne Pfadberechnung ist dieser Algorithmus ebenfalls geeignet.
Grenzen und Hinweise
- Langsamer als Dijkstra für nicht-negative Gewichte: O(VE) gegenüber O((V+E)logV)
- Weniger effizient für dünne Graphen im Vergleich zu anderen Algorithmen
- Erfordert, dass alle Kanten explizit aufgelistet sind, was ihn für implizite oder dynamische Graphen weniger geeignet macht
- Keine heuristische Führung zur Beschleunigung der Berechnung verfügbar
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Behandelt Graphen mit negativen Kantengewichten korrekt
- Erkennt Zyklen negativen Gewichts und verhindert fehlerhafte Ergebnisse für kürzeste Pfade
- Einfacher zu verstehen und zu implementieren als einige fortgeschrittene Algorithmen für kürzeste Pfade
- Garantiert das Finden kürzester Pfade in O(VE) Zeit
- Funktioniert auf gerichteten und ungerichteten Graphen (bei ungerichteten mit Vorsicht)
Anwendungen
- Erkennung von Währungsarbitrage: Identifizierung profitabler Zyklen in Wechselkursgraphen
- Netzwerk-Routing-Protokolle: Berechnung kürzester Pfade, bei denen Link-Kosten variieren oder negativ sein können
- Spieltheorie: Lösung von Problemen mit kürzesten Pfaden mit Strafkanten oder Diskontierungsfaktoren
- Robotik: Pfadplanung in Umgebungen mit abstoßenden Kräften (negative Gewichte)
- Wirtschaftliche Fahrplangestaltung: Optimierung der Stromerzeugung mit Kostenfunktionen, die negative Terme enthalten
- Telekommunikation: Finden optimaler Routen, wenn Link-Gewichte Verzögerungs- oder Qualitätsmetriken darstellen
So funktioniert es
So funktioniert es
Setzen Sie die Distanz zum Quellknoten auf Null und alle anderen Distanzen auf unendlich; optional setzen Sie alle Vorgänger auf Null.
Wiederholen Sie V-1 Mal: Für jede Kante (u, v) mit Gewicht w, falls distanz[u] + w kleiner ist als distanz[v], aktualisieren Sie distanz[v] und den Vorgänger von v.
Überprüfen Sie alle Kanten ein weiteres Mal; falls sich eine Distanz verbessert, existiert ein Zyklus negativen Gewichts. Geben Sie einen Fehler zurück oder identifizieren Sie den Zyklus entsprechend.
Häufige Fallstricke
- Das Vergessen der zusätzlichen Iteration zur Erkennung negativer Zyklen
- Annahme, dass der Algorithmus auf ungerichteten Graphen mit negativen Kanten korrekt funktioniert (kann virtuelle negative Zyklen erzeugen)
- Verwendung des Algorithmus, wenn Dijkstra ausreicht, was zu unnötigen Leistungseinbußen führt
Häufig gestellte Fragen
Warum benötigt der Algorithmus genau V-1 Iterationen?
Jeder Pfad in einem Graphen mit V Knoten hat höchstens V-1 Kanten. Durch V-1 Iterationen erlaubt der Algorithmus, dass sich Distanzinformationen durch den gesamten Graphen ausbreiten. Eine V-te Iteration wird nur dann Distanzen verbessern, wenn ein negativer Zyklus existiert.
Wie kann der Algorithmus negative Zyklen erkennen?
Nach Abschluss von V-1 Iterationen wird ein weiterer Relaxationsschritt durchgeführt. Wenn sich eine Distanz verringert, existiert ein negativer Zyklus. Die am Zyklus beteiligten Knoten können durch Rückverfolgung mittels Vorgängerzeigern identifiziert werden.
Was ist die Zeitkomplexität und wie verhält sie sich zu Dijkstra?
Bellman-Ford läuft in O(VE) Zeit, wobei V Knoten und E Kanten sind. Dijkstra läuft in O((V+E)logV) mit einem binären Heap. Bellman-Ford ist langsamer, behandelt aber negative Gewichte; Dijkstra ist schneller, erfordert aber nicht-negative Gewichte.
Kann Bellman-Ford auf ungerichteten Graphen mit negativen Gewichten arbeiten?
Technisch ja, aber er kann aufgrund der bidirektionalen Natur von Kanten irreführende negative Zyklen erzeugen. Besondere Sorgfalt ist erforderlich, um die Ergebnisse korrekt zu interpretieren. Für ungerichtete Graphen sollten alternative Ansätze in Betracht gezogen werden.
Verwandte Methoden
Quellen
Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.
DOI-Referenz öffnenKopiert.Ford, L. R. (1956). Network Flow Theory. RAND Corporation Paper P-923.
Publikationsreferenz öffnenKopiert.