networking - Bellman Ford 和 Dijkstra 算法之间的区别

Question

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

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

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

预先感谢您的帮助。

Answer 1

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

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

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

如果有 1 个以上的路径具有最小成本，则返回的实际路径取决于实现(即使对于相同的算法)。