Algorithms and Data Structures · Senior · Question 1 of 75
Why does Dijkstra's algorithm give wrong results with negative edge weights?
- 1Negative numbers can't be stored in a binary heap at all
- 2It loops forever whenever any weight is below zero
- ✓Correct answer: A finalized vertex could still get shorter via a negative edge
Explanation
Dijkstra assumes that once the closest vertex is taken from the queue, no later path can be shorter. A negative edge breaks that assumption. Bellman-Ford handles negative weights in O(V × E) and also detects negative cycles.