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

好的，这就是图表。我的源节点是1，目标节点是5

我的问题是。

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

提前感谢您的帮助。

4

3 回答 3

26

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

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

对于您的情况，就总成本而言，没有区别，因为图中的边具有非负权重。但是，通常使用 Dijkstra 算法，因为二进制堆的典型实现具有Theta((|E|+|V|)log|V|)时间复杂性，而 Bellman-Ford 算法具有O(|V||E|)复杂性。

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

于 2013-04-29T07:24:51.477 回答
4

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

于 2013-07-29T07:01:05.970 回答
0

Djikstra 算法是一种贪心技术，对于实现 bellmanford 算法，我们需要动态方法。

在 djikstra 算法中，我们在循环中对每个节点/顶点进行松弛，而在 bellmanford 算法中，我们只执行松弛|v-1| 次。

当边权重为正时，Dijkstra 算法适用于图，而在负边图的情况下失败，因为 bellmanford 算法比 djikstra 具有优势，即使边权重为负数，它也可以实现。

bellmanford 可以找到图形解决方案是否存在（即给定的有向图是否具有负权重循环），而 djikstra 算法无法做到这一点。

djikstra 算法的时间复杂度是 O(v^2) 当用线性数组实现时，O(e.log v) 当用二进制堆或斐波那契堆实现时，因为 bellmanford 算法有 O(|v| |e|) 时间复杂度.

于 2018-11-23T05:04:32.673 回答