SPFA同样是一种基于贪心的算法,看过之前一篇blog的读者应该可以发现,SPFA和堆优化版的Dijkstra如此的相似,没错,但SPFA有一优点是Dijkstra没有的,就是它可以处理负边的情况。
和Dijkstra的出发点不同,Dijkstra是从点入手的,而SPFA则是从边开始的,要不断的改变边,把点入堆,有的时候SPFA是比堆优化版的Dijkstra要慢的。
下面是程序,还是借助它来讲解,很容易理解,关键之处是一定要自己去试着编程。
#include<bits/stdc++.h>
using namespace std;
struct node{
int quan,qian,to;
}shu[];
int head[],ans,n,m,s,dis[];
bool vis[];
priority_queue<int> q;
void add(int x,int y,int z){
shu[++ans].qian=head[x];
shu[ans].quan=z;
shu[ans].to=y;
head[x]=ans;
}//链式前向星存储(前2篇中已经讲到)
void spfa(){
memset(dis,0x3f,sizeof(dis));
memset(vis,false,sizeof(vis));
q.push(s);//s入堆
dis[s]=;vis[s]=true;//s已经在堆中可以从此查找
while (q.size()!=){//如果堆中元素个数不为0那么还可以继续
int x=q.top();q.pop();//x为要查找的编号
vis[x]=false;//已经查找过了,但以后有可能还要更新,所以把它还原
int w=head[x];
while (w!=){
if (shu[w].quan+dis[x]<dis[shu[w].to]){//更新到shu[w].to这个点的最小值
dis[shu[w].to]=shu[w].quan+dis[x];
if (not vis[shu[w].to]) q.push(shu[w].to);//如果更新了,并且不在堆中,那么就入堆
}
w=shu[w].qian;
}
}
}
int main(){
cin>>n>>m>>s;
ans=;
for (int i=;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);//存边
}
spfa();
for (int i=;i<=n;i++){
if (dis[i]>='') cout<<"2147483647 ";
else cout<<dis[i]<<" ";
}
}
个人觉得不用优先队列,直接用普通的队列也是可以解决问题的。