专栏首页ACM算法日常对比 Dijkstra Bellman—Ford Spfa 最短路之间区别

对比 Dijkstra Bellman—Ford Spfa 最短路之间区别

先浅谈一下Dijkstra:

本质上Dijkstra是一种贪心,满足局部最优,每次找的是离起点最近的(保证了这个点的距离就是最短路),如果有负边权,当前找到的就不一定是最近的了。

所以这就是为什么Dijkstra不能处理负边权。

其次谈一下Bellman—Ford算法:

核心就是遍历N(这张图的点数)次,是每条边进行收敛的过程,如果有负环,每次进行松弛操作时都会被更新,源点距各个点的最小距离就会不停变小,不能被收敛,那就完蛋了.如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。

经过第一次遍历后,点B的值变为5,点C的值变为8。

这时,注意权重为-10的边,这条边的存在,导致点A的值变为-2。(8+ -10=-2)

第二次遍历后,点B的值变为3,点C变为6,点A变为-4。

正是因为有一条负边在回路中,导致每次遍历后,各个点的值不断变小。

所以这是无限循环的。

最后谈一下Spfa,其实就是队列里跑Bellman—Ford,原理是一样的没什么好谈的

const int n=100010,m=100010;
int head[n],ver[m],edge[m],next[m],d[n];
int n,m,tot;
queue<int>q;
bool v[n];
void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,next[tot]=head[x],head[x]=tot;
}
void spfa(){
      memset(d,0x3f,sizeof(d));
      memset(v,0,sizeof(v));//判断是否在队列中
      d[1]=0;v[1]=1;
      q.push(1);
      while(!q.empty()){
             int x=q.front();q.pop();
             v[x]=0;
             //扫边
             for(int i=head[x];i;i=next[i]){
                     int y=ver[i],z=edge[i];
                        if(d[y]>d[x]+z){
                                d[y]=d[x]+z;
                                if(!v[y]) q.push(y),v[y]=1;
                        }

             }
      }

}

最后:概括一下这几者之间的区别:

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:mxg

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode题解 | 78. 子集

    这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

    ACM算法日常
  • 图论建图

    图论建图无外乎邻接表建图和链式前向星建图,不要问我是怎么知道的,要是你的学校逼你打图论位的话你就知道了。

    ACM算法日常
  • 不同路径(动态规划)- leetcode 62

    最近在看leetcode的题目,都是面试题,需要面试的同学可以努力刷这里的题目,因为很多公司的面试笔试题都是参考这个上面的。相对OJ上的题目,感...

    ACM算法日常
  • 1061 判断题 (15 分)

    可爱见见
  • Java中实现找到两个数组交集的2种方法,开发实用

    1、用HashSet实现的解决方法 实例代码如下: public int[] intersection(int[] nums1, int[] nums2) { ...

    用户1289394
  • 数组的简单练习题

    1.将一个给定的整型数组转置输出, 例如: 源数组,1 2 3 4 5 6 转置之后的数组,6 5 4 3 2 1

    阮键
  • 洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

    具体来说,每次比较当前后缀和\(S_0\)的lcp,如果长度\(< N\)的话就从不合法的位置继续匹配

    attack
  • 回溯法求组合问题

    用户7727433
  • 【CodeForces 730H】Car Repair Shop

    模拟,先看从s[i]时刻开始修理,和之前i-1个是否冲突。如果冲突,就枚举每个s[j]+d[j]时刻开始,看是否冲突,再从中选择最小的时刻。

    饶文津
  • C++中动态申请数组

    动态申请一维数组 申请使用new,释放使用delete[] 可以通过数组名[下标]和*(数组名+下标)的方式访问数组

    卡尔曼和玻尔兹曼谁曼

扫码关注云+社区

领取腾讯云代金券