Question

Why doesn't Dijkstra's algorithm work with negative weights in graphs?

A) Dijkstra's algorithm assumes that negative weights may cause infinite loops.
B) Negative weights violate the assumption of non-negativity required by Dijkstra's algorithm.
C) Dijkstra's algorithm only works with acyclic graphs.
D) Negative weights cause the algorithm to prioritize incorrect paths.

Answer 1

Dijkstra's algorithm does not work with negative weights in graphs because it assumes non-negativity of weights. So, the correct answer is option a.

Step-by-step explanation:

Dijkstra's algorithm does not work with negative weights in graphs because it assumes non-negativity of weights. The algorithm works by continually selecting the vertex with the lowest distance and updating the distances of its adjacent vertices. When negative weights are present, this assumption is violated as there may exist a shorter path through a vertex with a negative weight, causing the algorithm to prioritize incorrect paths.

So, the correct answer is option a.