algorithm - Dijkstra算法= SSSP-LMLPHP
据我所知,dijkstra不能处理负边权为此,我们必须使用贝尔曼福特。
Belman Fords与负边缘权值和负循环很好地工作,这是无法从源获得的,否则它将返回MSG“负循环存在”。
但是,上述图与Dijkstra结合得很好,即使存在负边缘权重。那么,如何知道何时使用具有负边缘权重的dijkstra呢?是吗?
所想的是,dijkstra可以或不能处理负重边。
如果存在负循环,那么它将不起作用。但是,如果不存在,它可以或不能工作。
我说得对吗?帮我引路??

最佳答案

dijkstra的算法不能处理负边缘权值。这是因为一旦它将一个节点标记为“已访问”,它就假定到它的最短路径已经找到,并且不能更改,在具有负边(并且没有负循环)的图中很容易违反的不变量:

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

用Dijkstra的算法从A开始寻找最短路径将产生C的错误代价,2
你发布的图表也不起作用:考虑从dh的最短路径图中的Dijkstra将为路径(4)生成d->g->h,而成本为0的路径更便宜:d->a->b->c->h

关于algorithm - Dijkstra算法= SSSP,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/38801233/

10-11 22:33
查看更多