据我所知,dijkstra不能处理负边权为此,我们必须使用贝尔曼福特。
Belman Fords与负边缘权值和负循环很好地工作,这是无法从源获得的,否则它将返回MSG“负循环存在”。
但是,上述图与Dijkstra结合得很好,即使存在负边缘权重。那么,如何知道何时使用具有负边缘权重的dijkstra呢?是吗?
所想的是,dijkstra可以或不能处理负重边。
如果存在负循环,那么它将不起作用。但是,如果不存在,它可以或不能工作。
我说得对吗?帮我引路??
最佳答案
dijkstra的算法不能处理负边缘权值。这是因为一旦它将一个节点标记为“已访问”,它就假定到它的最短路径已经找到,并且不能更改,在具有负边(并且没有负循环)的图中很容易违反的不变量:
A
/ \
7/ \2
/ \
B------>C
-6
用Dijkstra的算法从A开始寻找最短路径将产生C的错误代价,
2
。你发布的图表也不起作用:考虑从
d
到h
的最短路径图中的Dijkstra将为路径(4
)生成d->g->h
,而成本为0的路径更便宜:d->a->b->c->h
关于algorithm - Dijkstra算法= SSSP,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/38801233/