Bellman-Ford算法和Dijkstra算法的区别

Question

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

好的，这是图表。我的起点节点是1，终点节点是5

我的问题是。

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

提前感谢您的帮助。

- Gaurav Gandhi

Answer 1

Bellman-Ford算法是一种单源最短路径算法，能够处理负权重的边，并且可以在图中检测到负环。

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

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

如果有多条路径具有最小成本，则返回的实际路径取决于实现方式(即使是相同的算法)。

- nhahtdh

---

我想补充一点，对于分布式节点网络，Dijkstra算法需要集中控制（需要全局开放列表等），而Bellman-Ford算法则不需要（每个节点只需更新邻居的变化）。它们在网络术语中分别被称为链路状态和距离向量算法。[希望这不会太模糊难懂...] - JasoonS

Answer 2

Dijkstra算法中的顶点包含了网络的全部信息。每个顶点并不只关心自身和邻居节点。相反，Bellman-Ford算法的节点只包含相关信息。这些信息允许该节点知道它可以连接哪些邻居节点以及关系来自哪个节点。Dijkstra算法比Bellman-Ford算法更快，但后者在解决一些问题时可能更有用，例如路径存在负权重的情况。

- bnsk

Answer 3

Djikstra算法是一种贪心技术，而实现Bellman-Ford算法需要动态方法。

在Djikstra算法中，我们在循环中放松每个节点/顶点，而在Bellman-Ford算法中，我们仅执行|v-1|次放松。

Dijkstra算法适用于边权为正的图，但在负边缘图的情况下失败，而Bellman-Ford算法具有优势，即可以在边缘权重被赋予负值时实现。

Bellman-Ford算法可以找到图形解决方案是否存在（即给定的有向图是否具有负权重循环），而Djikstra算法无法执行相同的操作。

当使用线性数组实现时，Djikstra算法的时间复杂度为O(v^2)，当使用二进制堆或斐波那契堆实现时，时间复杂度为O(e.log v)。而Bellman-Ford算法的时间复杂度为O(|v||e|)。

- Aman Mishra