Dijkstra算法= SSSP

Question

​

​

据我所知，dijkstra不能与负边权重一起工作。为此，我们必须使用行李员福特。

Bellman fords可以很好地处理负边权重和负循环，否则它将返回消息“负循环存在”。

但是，上面显示的这个图在dijkstra中工作得很好，即使存在负边权重。那么，如何知道何时使用具有负边权重的dijkstra？

我们认为，dijkstra可以或不能使用负权重边缘。如果存在负循环，那么它将不起作用。但如果不存在，它可以或不能工作。

我说的对吗？请指导我做这个?？

Answer 1

Dijkstra的算法不能在负边权值下工作。这是因为一旦它将一个节点标记为“已访问”，它就假设已经找到了到该节点的最短路径，并且不能改变，这是一个在具有负边(没有负圈)的图中很容易被违反的不变量：

       A
      / \
    7/   \2
    /     \
   B------>C
      -6

使用从A开始的Dijkstra算法寻找最短路径将为C，2产生错误的成本。

您发布的图也不起作用:考虑从d到h的最短路径。这张图上的Dijkstra将为路径生成4 (d->g->h)，而有一个成本为0的更便宜的路径：d->a->b->c->h

Answer 2

Dijkstra不能与负权重边一起工作。有一个名为Johnson的算法，它“重新加权”图中的所有边，最后使所有边都为正。但该算法称为bellman ford算法，其时间复杂度为O(V2logV + VE)。所以Dijkstra + Johnson的时间复杂度不是很好。但如果图形可以处理，也许你可以提前使用算法。附言:我为我糟糕的英语感到抱歉。

Answer 3

你是对的，Dijkstra将为负权重工作。然而，如果任一循环中的权重和为负，则该方法将不起作用。