带全负权边无负环图上运行Dijkstra算法能否找到最短路径？

Short answer: No, the standard Dijkstra's Algorithm cannot be relied on to find the correct shortest paths in this scenario. Here's why:

Core Assumption of Dijkstra's #

Dijkstra's works under the key assumption that once a node is extracted from the priority queue (and marked as "visited"), we have found the shortest possible path to that node. This holds true when all edge weights are non-negative—because any subsequent path to the visited node would have to add non-negative weights, making it longer than the already found path.

But when edges can have negative weights, this assumption breaks. Even if there are no negative cycles, a later path to a previously visited node could have a shorter (more negative) total weight, which Dijkstra's will ignore because it doesn't revisit nodes.

Example of Failure #

Let’s walk through a concrete example to see this in action:

• Nodes: S (source), A, B, C
• Edges:
  • S → A: weight -1
  • A → B: weight -1
  • B → C: weight -1
  • S → C: weight -2

The shortest path from S to C is S → A → B → C with total weight -3, which is shorter than the direct edge -2.

Here’s how Dijkstra’s processes this:

1. Initialize distances: dist[S] = 0, others are ∞.
2. Extract S from the queue, relax edges: dist[A] = -1, dist[C] = -2. Queue now has A (-1) and C (-2).
3. Extract C (smallest current distance), mark it as visited. No edges from C to process.
4. Extract A, relax edge to B: dist[B] = -2. Queue now has B (-2).
5. Extract B, relax edge to C: the new possible distance is -2 + (-1) = -3, which is shorter than the current dist[C] = -2. But since C is already marked as visited, Dijkstra’s skips updating this distance.

The result? Dijkstra’s returns -2 as the shortest path to C, which is wrong.

What to Use Instead? #

For graphs with negative edge weights (but no negative cycles), algorithms like Bellman-Ford or the Shortest Path Faster Algorithm (SPFA) are appropriate. These algorithms don’t make the same non-negativity assumption and can correctly handle such cases by allowing multiple relaxations of nodes until no shorter paths are found.

内容的提问来源于stack exchange，提问作者jjpark