Bellman_Ford算法和SPFA算法
给定一张有向图,若对与图中的某一条边(x,y,z),有dist[y] <= dist[x] + z 成立,则称该边满足三角不等式。若所有边都满足三角不等式,则dist数组就是所求最短路。
Bellman_Ford算法的基本流程:
1.扫描所有边(x,y,z),若dist[y] > dist[x] + z,则用dist[y]更新。
2.重复所有步骤,真到没有更新操作发生。
实际上,SPFA算法在国际上统称为:”队列优化版的Bellman_Ford算法”。
SPFA算法的基本流程:
1.建立一个队列,最初队列中只含有起点1。
2.取出都节点x,扫描它的所有出边(x,y,z),若dist[y] > dist[x] + z,则用dist[y]更新。同时,若y不在队列中,则把y入列。
3.重复上面步骤,直到队列为空为止。
即使图中存在长度为负的边,Bellman_Ford和SPFA算法也能够成功。
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1000010,M = 1000010;
int head[N],ver[N],edge[N],next[N],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.size()){
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;
}
}
}
}
int main(){
cin >> n >> m;
for(int i=1;i<=m;i++){
int x,y,z;
cin >> x >> y >> z;
add(x,y,z);
}
spfa();
return 0;
}