Bellman Ford 和 Dijkstra 算法的区别

贝尔曼福特算法

与其他动态规划问题一样，该算法以自下而上的方式计算最短路径。它首先计算路径中最多有一条边的最短距离。然后，它计算最多有 2 条边的最短路径，依此类推。在外循环的第 i 次迭代之后，计算最多有 i 条边的最短路径。可以有最大值 |V| – 任何简单路径中的 1 条边，这就是外循环运行 |v| 的原因- 1次。这个想法是，假设如果我们计算了最多有 i 个边的最短路径，则没有负权重循环，那么对所有边的迭代保证给出最多有 (i+1) 个边的最短路径

Dijkstra 算法

Dijkstra 的算法与 Prim 的最小生成树算法非常相似。与 Prim 的 MST 一样，我们生成一个以给定源为根的 SPT(最短路径树)。我们维护两组，一组包含包含在最短路径树中的顶点，另一组包含尚未包含在最短路径树中的顶点。在算法的每一步，我们都会找到一个顶点，它在另一个集合(尚未包含的集合)中并且与源的距离最小。

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

Bellman Ford 算法和 Dijkstra 算法都是单源最短路径算法，即都确定了图的每个顶点到单个源顶点的最短距离。但是，它们之间存在一些关键差异。我们遵循 Bellman Ford 算法中的动态规划方法和 Dijkstra 算法中的贪婪方法。让我们看看这两种技术之间的其他主要区别

Bellman Ford 算法	Dijkstra 算法
贝尔曼福特算法在存在负权重边缘时工作，它还检测负权重循环。	Dijkstra 算法在权重边缘为负时可能有效，也可能无效。但当权重循环为负时，绝对行不通。
结果包含顶点，其中包含有关它们连接到的其他顶点的信息。	结果包含包含有关网络的全部信息的顶点，而不仅仅是它们连接的顶点。
它可以很容易地以分布式方式实现。	它不能以分布式方式轻松实现。
它比 Dijkstra 的算法更耗时。它的时间复杂度是 O(VE)。	它花费的时间更少。时间复杂度为 O(E logV)。
采用动态规划方法来实现该算法。	采用贪心方法来实现该算法。