Why is Dijkstra's algorithm not suitable for graphs with negative weight edges?

Question

BlackTom AI · Accepted Answer

Dijkstra's algorithm assumes nonnegative edge weights, so its greedy choice (extracting the currently shortest tentative distance and marking it final) is guaranteed to be optimal only under that assumption.

1) Relevant knowledge points and concepts
- Greedy correctness: when a node v is extracted with minimal tentative distance d[v], no later path can produce a smaller distance if all edges have nonnegative weights.
- Relaxation: edges are relaxed to improve tentative distances.
- Negative edges or negative cycles can invalidate the greedy-finality property or allow arbitrarily smaller path costs by cycling.

2) Step-by-step reasoning
- Start with source s and tentative distances d[] (d[s]=0, others = ∞).
- Dijkstra repeatedly extracts the vertex u with smallest d[u] and treats d[u] as final.
- This finality step relies on the fact that any path reaching u through another yet-unprocessed vertex must be at least as large as d[u] because remaining edge weights are ≥ 0.
- If a negative edge or a negative cycle exists, a path discovered later can reduce d[u] after u was already finalized. That breaks the algorithm’s invariant.

3) Example (intermediate steps)
Consider S→A weight 0, A→B weight 1, B→A weight -2. Initialize: d[S]=0, d[A]=∞, d[B]=∞.
- Relax S→A: d[A]=0. Extract A (d[A]=0) and finalize A.
- Relax A→B: d[B]=1. Extract B (d[B]=1).
- Relax B→A: new distance to A = d[B]+(-2) = 1 + (-2) = -1 < finalized d[A]=0.
A was already finalized, but a shorter path to A exists; Dijkstra cannot accommodate this, so its result is incorrect. If a negative cycle exists, repeated traversal can decrease costs indefinitely (loop infinitely making the path shorter).

4) Why the correct answer is correct
The provided answer states: "When chosing the smallest path, it may loop infinitly making that path shorter." This captures that negative weights (especially negative cycles) undermine Dijkstra’s greedy choice: paths can be improved later or decreased without bound by looping.

5) Why other options are incorrect
- "It cannot handle large graphs efficiently": false — Dijkstra is efficient (e.g., O((V+E) log V) with a heap).
- "A negative weight can make the math unstable": incorrect — the issue is algorithmic correctness, not numeric instability.
- "It cannot handle graphs with cycles": wrong — cycles are fine if weights are nonnegative.
- "It does not work with undirected graphs": wrong — undirected graphs are supported (treated as bidirectional edges).

6) Conclusion
The explanation confirms the provided correct answer: "When chosing the smallest path, it may loop infinitly making that path shorter".

Why is Dijkstra's algorithm not suitable for graphs with negative weight edges?单项选择题

类似问题

What is the time complexity of Dijkstra's algorithm using a priority queue (min-heap) implemented with a binary heap?

狄克斯特拉算法在社交网络中用于判定： Dijkstra’s Algorithm is used in social network for determining

Which of the following properties of a weighted graph G will prevent the use of Dijkstra's algorithm for finding shortest paths in G?

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单