洛谷P3371单源最短路径SPFA算法

fnbk 2018-07-17 原文

SPFA同样是一种基于贪心的算法，看过之前一篇blog的读者应该可以发现，SPFA和堆优化版的Dijkstra如此的相似，没错，但SPFA有一优点是Dijkstra没有的，就是它可以处理负边的情况。

和Dijkstra的出发点不同，Dijkstra是从点入手的，而SPFA则是从边开始的，要不断的改变边，把点入堆，有的时候SPFA是比堆优化版的Dijkstra要慢的。

下面是程序，还是借助它来讲解，很容易理解，关键之处是一定要自己去试着编程。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct node{
 4     int quan,qian,to;
 5 }shu[500010];
 6 int head[10010],ans,n,m,s,dis[10010];
 7 bool vis[10010];
 8 priority_queue<int> q; 
 9 void add(int x,int y,int z){
10     shu[++ans].qian=head[x];
11     shu[ans].quan=z;
12     shu[ans].to=y;
13     head[x]=ans;
14 }//链式前向星存储（前2篇中已经讲到）
15 void spfa(){
16     memset(dis,0x3f,sizeof(dis));
17     memset(vis,false,sizeof(vis));
18     q.push(s);//s入堆
19     dis[s]=0;vis[s]=true;//s已经在堆中可以从此查找
20     while (q.size()!=0){//如果堆中元素个数不为0那么还可以继续
21         int x=q.top();q.pop();//x为要查找的编号
22         vis[x]=false;//已经查找过了，但以后有可能还要更新，所以把它还原
23         int w=head[x];
24         while (w!=0){
25             if (shu[w].quan+dis[x]<dis[shu[w].to]){//更新到shu[w].to这个点的最小值
26                dis[shu[w].to]=shu[w].quan+dis[x];
27                if (not vis[shu[w].to]) q.push(shu[w].to);//如果更新了，并且不在堆中，那么就入堆
28             }
29             w=shu[w].qian;
30         }
31     }
32 }
33 int main(){
34     cin>>n>>m>>s;
35     ans=0;
36     for (int i=1;i<=m;i++){
37         int a,b,c;
38         cin>>a>>b>>c;
39         add(a,b,c);//存边
40     }
41     spfa();
42     for (int i=1;i<=n;i++){
43           if (dis[i]>='100000') cout<<"2147483647 ";
44         else cout<<dis[i]<<" ";
45     }
46 }