当前位置:   article > 正文

Bellman-ford算法_bellmanford算法

bellmanford算法

一、Bellman-ford算法简介

           Bellman-ford算法是一种求解“单源最短路径”算法,单源最短路就是求一个源点到其他结点的最短路径。而Bellman-ford算法最核心的思想就是“松弛操作”。我们用下图来具体操作一下Bellman-ford。

 

二、Bellman-ford算法详细解释

1.算法具体操作

     首先,我们定义一个dis[ i ]数组, dis数组的意义是源点到其他点的经过边数不超过k(松弛操作次数)的最短距离。 假定 1号顶点是源点,则初始化dis[1] = 0; 其他点的距离初始化为无穷大

 

         然后开始第一轮松弛,遍历全部边,首先遍历第一条边进行松弛 2 - > 3, 其权值为2。松弛操作就是 : 试一试用 源点 到2号顶点 的距离 加上  2 -> 3的权值,能否缩小 源点 到 3号顶点 的距离。 现在开始进行松弛, 我们发现dis[2] 和 dis[3] 都是无穷大, 那么此时 源点 到 2号顶点 ,3号顶点 的距离都是无穷大。说明我们不能达到2号顶点,所以我们不可以使用 2->3 这条边进行松弛。

        然后遍历第2条边, 1 -> 2 ,权值-3。 此时我们发现可以通过 这条边来松弛 源点 到 2号结点 的距离,因为 dis[2] > dis[1] + -3(权值)。第一轮松弛结束后,得到新的结果 ,如下图

           然后我们再次遍历所有边,进行第二轮松弛, 也是首先遍历第一条边 2 -> 3 权值为2. 我们此时发现通过这条边可以松弛 源点 到 3号顶点 的距离, 因为  dis[3] > dis[2] + 2 并且 此时 dis[2]是可抵达的。

        为什么第一轮松弛操作无法松弛dis[3], 而第二次轮操作却成功松弛呢 ? 

        因为经过第一轮松弛操作 dis[2] 已经改变了,已经可抵达了,缩小了,松弛成功了。

换句话说 : 经过第一轮松弛,我们就找到了源点到其他顶点经过一条边最短路。 经过第二轮松弛, 我们就找到了源点到其他顶点经过两个条边的最短路。 那么经过多少轮松弛才可以得到源点到其余顶点的最短路呢 ?

        应该是经过 (顶点数 - 1 )轮松弛,就可以找到其余所有顶点的最短路。(这里需要多思考,大家可以手动模拟一下) 

 

2.算法具体代码

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  4. const int N = 100, M = 100;
  5. //读入点数 和 边数
  6. int n, m;
  7. //dis数组, 记录上次状态的dis数组
  8. int dis[N];
  9. //存储边的结构体数组
  10. struct Edge {
  11. int a, b, w;
  12. }edges[M];
  13. void bellmanford() {
  14. //初始化dist数组
  15. memset(dis, 0x3f, sizeof(dis));
  16. dis[1] = 0;// 1是源点
  17. //经过 n - 1次松驰
  18. //对所有边进行一次松弛操作,就求出了源点到所有点,经过的边数最多为1的最短路
  19. //对所有边进行两次松弛操作,就求出了源点到所有点,经过的边数最多为2的最短路
  20. //....
  21. //对所有边进行n- 1次松弛操作,就求出了源点到所有点,经过的边数最多为n - 1的最短路
  22. for(int i = 0; i < n - 1; i++) {
  23. //遍历所有边
  24. for(int j = 0; j < m; j++) {
  25. int a = edges[j].a, b = edges[j].b, w = edges[j].w;
  26. if(dis[a] != 0x3f3f3f3f && dis[b] > dis[a] + w) //松弛操作
  27. dis[b] = dis[a] + w;
  28. }
  29. }
  30. }
  31. int main() {
  32. //读入点数,边数
  33. cin >> n >> m;
  34. //读入边
  35. for(int i = 0; i < m; i++) {
  36. int a, b, w;
  37. cin >> a >> b >> w;
  38. edges[i] = {a, b, w};
  39. }
  40. //调用 bellman - ford算法
  41. bellmanford();
  42. //打印dis数组
  43. for(int i = 1; i <= n; i++)
  44. cout << dis[i] << " ";
  45. cout << endl;
  46. system("pause");
  47. return 0;
  48. }
  49. /*
  50. 输出样例
  51. 5 5
  52. 2 3 2
  53. 1 2 -3
  54. 1 5 5
  55. 4 5 2
  56. 3 4 3
  57. 输出样例
  58. 0 -3 -1 2 4
  59. */


总结及其深入

        1. bellman-ford是可以进行优化的,首先不一定进行 n - 1轮松弛操作才会求出最短路。也许再 n - 3轮的时候就求出了。而且每次松弛操作,不一定成功。比如 2 - > 3 权值为2这条边。我们在第二轮才松弛了 dis[3] , 因为只有松弛了dis[2]才能松弛dis[3] :)。所以我们可以用队列记录被松弛顶点,然后通过该顶点来松弛其他相邻顶点。这就是SPFA(Shortest Path Fast Algorithm)算法。读者可以自己实现一下哦。SPFA的最差时间复杂度是O(NM),但是正常情况下很快的。

      2.bellman-ford算法可以检测负权环。正常情况,最差 n - 1次松弛 就可以求出最短路。但是如果存在负权环,是没有最短路的,我们可以通过反复走这条边,来缩短距离。如果要检测负权环,我们只需要在bellman-ford运行完成后,再进行一轮松弛操作。如果松弛操作成功,那么证明有负权环。

        3.最后希望大家变得更强:)。如文章有错误,烦请指出~

参考资料

        《啊哈算法》

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/423307
推荐阅读
相关标签
  

闽ICP备14008679号