如果存在一个加权图 G，并且所有权重都是0，Dijkstra算法是否仍然找到最短路径？如果是，为什么？
根据我对算法的理解，如果没有边权重，Dijsktra 的算法将像普通的BFS 一样运行，但我希望得到一些说明。
最佳答案
解释
根据算法的定义，Dijkstra 本身对 0 权重没有问题。它只会在负权重时出现问题。
因为在每一轮中，Dijkstra 都会结算一个节点。如果您稍后发现负权重边，这可能会导致到达该已解决节点的较短路径。然后节点需要未解决，Dijkstras 算法不允许(并且会破坏算法的复杂性)。如果您看一下实际的算法和一些插图，就会明白这一点。
Dijkstra 在这样一个全零图上的行为与所有边都具有不同但相同的值一样，例如 1(除了得到的最短路径长度)。 Dijkstra 将简单地访问所有节点，没有特定的顺序。基本上，就像普通的广度优先搜索。
详情
看看Wikipedia的算法描述:
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 时，您就解决了它。也就是说，你说到这个节点的最短路径现在是已知的。但这意味着您不会再将 17 行中的 u 视为某个其他节点的邻居(因为它不再包含在 Q 中) .
对于负值，您稍后可能会发现到该节点的更短路径(由于负权重)。您需要在算法中再次考虑 u，并重新执行所有依赖于先前到 u 的最短路径的计算。因此，您需要添加 u 以及从 Q 中删除的所有其他节点，这些节点在返回 Q 的最短路径上有 。u
特别是，您需要考虑可能通向目的地的所有边，因为您永远不知道某些讨厌的-1_000_000 加权边隐藏在哪里。
下面的例子说明了这个问题:
Dijkstra 将红色路径声明为从A 到C 的最短路径，长度为0。但是，还有一条更短的路径。它标记为蓝色，长度为 99 - 300 + 1 = -200。
使用负权重，您甚至可以创建更危险的场景，负循环。这是图中总权重为负的循环。然后，您需要一种方法来停止一直沿循环移动，无休止地降低当前的体重。
注意事项
在无向图中，权重为 0 的边可以被消除，节点可以被合并。它们之间的最短路径的长度始终为 0。如果整个图只有 0 权重，则该图可以只合并到一个节点。每个最短路径查询的结果都只是0。
如果在两个方向上都有这样的边，那么对于有向图也是如此。否则，您将无法进行优化，因为您会更改节点的可达性。
关于algorithm - Dijkstra 算法可以在权重为 0 的图上工作吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49460439/