algorithm - 我可以将 Dijkstra 算法用于负加权图吗？

Question

我知道贝尔曼福特算法适用于负加权图，但我开发了一个运行良好的 Dijkstra 算法代码。但是当我插入负加权边缘时它会失败。任何解决方案？

Answer 1

我认为我们不能这样做，因为 Dijkstra 算法不会找到到达目标顶点的最终方法，因为它可能会陷入循环，它不是为负加权图制作的，你应该使用 bellman ford 算法

Answer 2

实际上，在特殊情况下是可能的。如果存在负长度的边，Dijkstra 算法将失败。但是，如果所有边的长度都是负数，那么您可以反转所有边的长度并使用该算法找到图的两个顶点之间的最长路径（该路径将表示原始图中的最短路径）。

但在一般情况下，正如您所说，不可能使用 Dijkstra。如果没有负长度的循环，则应使用 Bellman-Ford 算法。如果你不能保证没有负长度的循环，那么问题是NP 完全的并且没有已知的多项式算法。

Answer 3

正如您所说，Bellman Ford 是在具有负权重的图中找到最短路径的首选算法。在这种情况下使用 Dijkstra 算法的问题在于，Dijkstra 假设图中从 s 到 t 的所有可能子路径必须小于目标子路径，当添加负边权重时，这不一定是正确的。

Answer 4

如果所有边权重都是正数，则可以保证向路径添加更多边会使其更长。知道了这一点，Dijkstra 的算法将丢弃任何比它找到的到某个顶点的最短路径更长的路径，因为长路径不可能比短路径短。

但是，如果存在负边权重，则此假设不正确，因为我们可能有一条非常长的路径 P 被我们丢弃，但是在路上的某个地方，P 可以通过一个非常负的边并变得比您当前拥有的最短路径更短. 因此，我们不能保证我们找到的路径在算法所依赖的 Dijkstra 算法的任何阶段都是最短的。