Why can Dijkstra’s shortest-path algorithm give wrong results on a graph with negative edge weights?
Correct answer C. It finalises a vertex's distance when the vertex is removed from the queue, assuming later paths cannot be shorter
Explanation
Dijkstra greedily fixes the closest unsettled vertex, which is safe only if adding edges can never reduce a path's length. A negative edge found later could create a shorter route to a vertex already settled, and the algorithm will not revisit it. Bellman-Ford handles negative weights and detects negative cycles. Dijkstra itself works fine on directed graphs and on graphs with cycles.
Answer checked How we write and check questions
Discussion