什么时候Dijkstra和Bellman-Ford算法都找不到最短路径？

Question

我知道Dijkstra在边权重为负的情况下会失败，但何时两种算法都会失败？

Answer 1

如果存在负循环(从源头上可以到达)，可以认为贝尔曼-福特失败了。负循环的主要问题是，你可以继续遍历它，减少路径的成本，因此不存在到某些顶点的有限最短路径(因此，Bellman-Ford是否真的失败是有争议的-它可以检测到这些循环)。

Dijkstra的算法对于负循环也会有类似的问题(更不用说处理负边权重的更一般的问题了)。

另一种情况可能是无法到达的顶点，但同样可以检测到它们是无法到达的。

Answer 2

如果图包含负循环，并且该循环可以从源节点到达，而目的节点可以从该循环到达，则这两种算法都不会找到最短路径。在这种情况下，没有最短路径-您可以在循环中执行无限次迭代，从而始终减少路径长度。

Answer 3

由于如果存在负循环，则不存在最短路径，而Bellman-Ford可以检测到负循环，因此您可以争辩说，它永远不会失败。(同样，因为您可以检测到两个顶点之间何时没有路径)