GraphalgorithmenAdvanced
Bellman-Ford-Algorithmus
Kurzester-Pfad-Algorithmus von einer Quelle, der negative Gewichte behandelt und negative Zyklen erkennt. Entspannt alle Kanten V-1 Mal, um korrekte Distanzen auch mit negativen Gewichten zu garantieren. Wesentlich fur Wahrungsarbitrage-Erkennung, Netzwerk-Routing mit variierenden Kosten und Situationen, in denen Dijkstras Algorithmus versagt. Tauscht Geschwindigkeit gegen Flexibilitat.
#graph#shortest-path#negative-weights#dynamic-programming
Complexity Analysis
Time (Average)
O(V × E)Expected case performance
Space
O(V)Memory requirements
Time (Best)
O(V × E)Best case performance
Time (Worst)
O(V × E)Worst case performance
📚 CLRS Reference
Introduction to Algorithms•Chapter 24•Section 24.1
Loading...
Implementation