Question

Dijkstra's algorithm fails for graphs with _______.

• A. Negative weights
• B. Disconnected components
• C. Directed edges
• D. Self-loops

Hint:

When working with graphs that have negative edge weights, use the Bellman-Ford algorithm instead of Dijkstra’s algorithm, as it handles negative weights.

Answer 1

The Correct Option is A

Dijkstra's algorithm is based on the assumption that all edge weights are non-negative. If a graph contains negative weights, Dijkstra’s algorithm may not work correctly because it doesn't handle situations where a path to a vertex becomes shorter after a vertex is already processed. 
Hence, Dijkstra's algorithm fails in graphs with negative edge weights.