Dijkstra 算法 = SSSP

Question

据我所知，dijkstra 不能使用负边权重。为此，我们必须使用 bellman ford .

Bellman fords 可以很好地处理负边权重和负循环，否则无法从源中获取它们，它将 return 一条消息 "Negative cycles exist".

但是，上面显示的这张图适用于 dijkstra ，即使存在负边权重也是如此。那么，如何知道何时使用负边权重的 dijkstra ??

什么是 think ，dijkstra 可以或不能使用负权重边。如果存在负循环，则它不起作用。但如果不存在，它可以或不能工作。

我说的对吗？？请为此指导我 ??

Answer 1

你是对的，Dijkstra 将适用于负权重。但是，如果任何循环中的权重之和为负，它将不起作用。

Answer 2

Dijkstra 算法无法处理负边权重。这是因为一旦它将一个节点标记为 "visited"，它就会假设已经找到了到它的最短路径，并且不能更改，在具有负边（并且没有负循环）的图中很容易违反不变量：

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

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

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

Answer 3

Dijkstra 无法处理负权重边。有一个叫约翰逊的算法，它"re-weight"图中所有的边，最后让所有的边都为正。但是算法调用了bellman ford算法，时间复杂度为O(V2logV + VE)。所以Dijkstra + Johnson的时间复杂度不好。但是如果可以处理图形，也许你可以提前使用算法。 PS: 对不起我的英语不好

Answer 4

检查以下代码

    import networkx as nx
    g = nx.Graph()
    g.add_edge(1, 2, weigbt=-10)
    g.add_edge(2, 3, weight = -5)
    g.add_edge(1, 3, weight =-6)
    print(nx.single_source_dijkstra(g, 1, 3))

无论你的所有边都是正的还是负的，Dijkstra SSSP 都会给你相同的答案。但是，这并不意味着对于任何具有负边的图，Dijkstra 最短路径可能会在负边的情况下给出正确答案，但这并不意味着它会给出正确答案。

Dijkstra 算法 = SSSP

Dijkstra Algorithm = SSSP

algorithm

dijkstra