グラフアルゴリズムAdvanced
Bellman-Ford Algorithm
Single-source shortest path algorithm that handles negative weights and detects negative cycles. Relaxes all edges V-1 times to guarantee correct distances even with negative weights. Essential for currency arbitrage detection, network routing with varied costs, and situations where Dijkstra's algorithm fails. Trades speed for flexibility.
#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