0

我知道 Dijkstra 的算法只能用于正边长度，而当图形也有负边时，可以使用 Bellman-Ford。

不过，假设我们有一个只有正边的图。Bellman-Ford 会给出与 Dijkstra 相同的结果吗？

4

2 回答 2

2

是的，它会给出相同的结果。但是，它会运行得更慢，因为它也可以用于具有负边的图（受制于不存在负循环）。如果您查看 BF 正确性的证明，则不会假设某些边是负的。

于 2015-06-06T20:00:18.890 回答
0

我想在 Ami Tavory 的回答中添加一些内容。如果您可以检测到在任何通道中没有节点值更新，然后从那里返回，Bellman-ford 的算法可以更快一点。如果没有节点更新，则证明每次节点遍历都完成。

于 2015-06-16T18:28:00.697 回答