贝尔曼福特算法
与其他动态规划问题一样，该算法以自下而上的方式计算最短路径。它首先计算路径中最多有一条边的最短距离。然后，它计算最多有 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)。 |
| 采用动态规划方法来实现该算法。 | 采用贪心方法来实现该算法。 |
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/263995.html