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|)复杂性.

如果有多个路径具有最小成本,则返回的实际路径取决于实现(即使对于相同的算法).