Bellman Ford和Dijkstra算法的区别

2   1 
1----------2---------4 
|   |   | 
|3   |3  |1 
| 6  |   | 
3---------5 ---------

好吧，这就是图。我的源节点是1和目标节点是5Bellman Ford和Dijkstra算法的区别

我的问题是。

这两种算法是否会给出相同的输出？也就是说，都会返回1->2->4->5？（除dijkstra不允许负重）

在此先感谢您的帮助。

来源

2013-04-29 Gaurav Gandhi

Bellman-Ford算法是一种单源最短路径算法，它允许负边权重并可以检测图中的负周期。

Dijkstra算法也是另一种单源最短路径算法。但是，所有边的权重必须是非负的。

对于您的情况，就总成本而言，不存在差异，因为图中的边具有非负权重。但是，通常使用Dijkstra算法，因为典型的二进制堆实现具有时间复杂度，而Bellman-Ford算法具有复杂度。

如果有超过1条路径具有最低成本，则返回的实际路径与实现相关（即使对于相同的算法）。

来源

2013-04-29 07:24:51 nhahtdh

+1完美答案。 – Mehrdad 2013-04-29 07:26:43

我想补充一点，对于分布式节点网络，Dijkstra's需要集中控制（您需要有一个全局打开列表等），而Bellman-Ford不会（每个节点只是更新邻居的变化）。它们在网络术语中分别称为链接状态和距离矢量算法。 [我希望这不是太模糊了解...] – JasoonS 2016-08-13 22:26:28

Dijkstra算法中的顶点包含网络的全部信息。没有这样的事情，每个顶点只关心自己和邻居。另一方面，Bellman-Ford算法的节点只包含与之相关的信息。该信息允许该节点相互了解哪些邻居节点可以连接以及该关系来自哪个节点。 Dijkstra算法比Bellman-Ford算法更快，但第二种算法对于解决一些问题（如路径负权重）可能更有用。

来源

2013-07-29 07:01:05 bnsk

Bellman Ford和Dijkstra算法的区别

回答

相关问题