Algorithms and Data Structures · Senior · Question 2 of 75
What extra capability does Bellman-Ford have compared with Dijkstra?
- 1It finds a minimum spanning tree as a side effect
- ✓Correct answer: It works with negative weights and detects negative cycles
- 3It runs faster on every graph, at O(V + E)
Explanation
It relaxes all edges V - 1 times; if a V-th pass still improves a distance, there's a negative cycle. The price is O(V × E), much slower than Dijkstra's O((V + E) log V).