SPFA算法简介
全名为shortest path faster algorithm(最短路径快速算法)算法复杂度是与边数成正比
实现思路:
1)对每个结点建立数组 dis和vis
2)距离初始化位INF
3) dis[s]=0 vis[s]=0 s为起点
4) while 循环 queue不为空 不断查找队头松弛结点(缩短路径)的结点,并将其入队push vis->true,队头查找完后出队(vis->false)
代码实现:
SPFA
int vis[100010];
int dis[100010];
struct node{
int to;
int val;
};
int n,m;
vector<node>a[1000010];
void SPFA(int s){
for(int i=1;i<=n;i++){
dis[i]=1000000;
}
queue<int> p;
p.push(s);
dis[s]=0;
vis[s]=1;
while (!p.empty()) {
int u=p.front();
p.pop();
vis[u]=false;
for(int i=0;i<a[u].size();i++){
if(dis[a[u][i].to]>(dis[u]+a[u][i].val)){
dis[a[u][i].to]=dis[u]+a[u][i].val;
p.push(a[u][i].to);
vis[a[u][i].to]=1;
}
}
}
}