先浅谈一下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;
}
}
}
}
最后:概括一下这几者之间的区别: