Dijkstra's algorithm is guaranteed to produce correct shortest paths under which condition?

• A. All edge weights are non-negative
• B. All edges are directed
• C. The graph is acyclic
• D. All edge weights are equal

Answer: (A)

The key idea is that Dijkstra’s algorithm relies on non-negative edge weights so that once a vertex is chosen as having the smallest tentative distance, that distance is truly the shortest from the source. With non-negative weights, any path to that vertex that goes through any still-unvisited vertex would have to add a non-negative amount to the current distance. That means you can’t later find a shorter route to that vertex by going through unvisited vertices, so you can “lock in” the distance and keep it final.

If all edge weights are non-negative, the algorithm’s process of repeatedly extracting the closest unsettled vertex and relaxing its outgoing edges preserves this invariant, ensuring correctness. The other conditions don’t guarantee correctness alone: the algorithm works on directed graphs as well as undirected ones, it doesn’t require acyclicity, and having equal weights is just a special case of non-negative weights.