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