Dijkstra算法能够处理权重为0的图吗？

Question

Dijkstra算法能够处理权重为0的图吗？

algorithmdijkstrabreadth-first-searchpath-finding

8

如果存在一张带权图G，且所有权重都为0，Dijkstra算法是否仍然能找到最短路径？若是，为什么？

根据我对算法的理解，如果没有边权，则Dijsktra算法会像普通BFS一样运行，但是我希望能有些澄清。

- danielschnoll

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zabuzard · Accepted Answer

解释

根据算法定义，Dijkstra本身对0权重没有问题。它只在负权重时出现问题。

由于在每一轮中，Dijkstra都会“定居”一个节点。如果您后来发现了一个负权重的边，这可能导致到达该定居节点的更短路径。那么该节点将需要“取消定居”，但是Dijkstra算法不允许这样做（并且这会破坏算法的复杂性）。如果您查看实际算法和一些示例，就会变得清晰。

Dijkstra在这样的“全零”图上的行为与所有边缘具有不同但相同值（例如1）的情况相同（除了最短路径长度的结果）。 Dijkstra将仅按任意顺序访问所有节点。基本上像普通的广度优先搜索。

详情

从维基百科上查看算法描述：

 1 function Dijkstra(Graph, source):
 2
 3     create vertex set Q
 4
 5     for each vertex v in Graph:           // Initialization
 6         dist[v] ← INFINITY                // Unknown distance from source to v
 7         prev[v] ← UNDEFINED               // Previous node in optimal path from source
 8         add v to Q                        // All nodes initially in Q (unvisited nodes)
 9
10     dist[source] ← 0                      // Distance from source to source
11      
12     while Q is not empty:
13         u ← vertex in Q with min dist[u]  // Node with the least distance
14                                           // will be selected first
15         remove u from Q 
16          
17         for each neighbor v of u:         // where v is still in Q.
18             alt ← dist[u] + length(u, v)
19             if alt < dist[v]:             // A shorter path to v has been found
20                 dist[v] ← alt 
21                 prev[v] ← u 
22
23     return dist[], prev[]

负值的问题在于第15行和第17行。当你移除节点u时，你会将其“settle”。也就是说，你已经知道了到达该节点的最短路径。但这意味着你不会再将u作为其他节点的邻居来考虑（因为它不再包含在Q中）。

如果存在负值，那么后面可能会发现一条更短的路径（由于负权重）。你需要重新考虑算法中的u并重新计算所有依赖于先前到u的最短路径的计算。因此，你需要将u和从Q中删除的每个其他节点（其最短路径上有u）添加回Q中。

特别地，你需要考虑所有可能导致你的目标的边缘，因为你永远不知道哪些难缠的-1_000_000加权边缘藏在哪里。

以下示例说明了这个问题：

Dijkstra将宣称从A到C的最短路径为红色，长度为0。然而，存在一条更短的路径，标记为蓝色，长度为99 - 300 + 1 = -200。

使用负权重，甚至可以创建一个更危险的情况，即负环。这是图中具有负总权值的一个循环。你需要找到一种方法来停止沿着该循环移动，无休止地降低当前权重。

笔记

在无向图中，权重为0的边可以被消除，节点可以被合并。它们之间的最短路径总是长度为0。如果整个图只有0权重，则可以将该图合并为一个节点。每个最短路径查询的结果都是0。

对于有向图，如果两个方向上都有这样的边，则同样适用。否则，您不能进行此优化，因为会改变节点的可达性。