SPFA 算法详解

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=10000;
 4 const int inf=0x3f3f3f3f;//
 5 int dis[N],tu[N][N],b[N][N];//注意不能这样初始化：dis[N]={inf}；！！dis[i]存1点到各点的最短距离，
 6 bool vis[N];//tu[]存各点间的边，vis【i】标记i点是否在队列里
 7 int n,m;
 8 void spfa(int s)//spfa算法
 9 {
10     for (int i=0;i<=n;i++)
11     {
12         dis[i]=inf;
13     }//dis【】到各点的距离先初始化为一个极大的值
14     memset(vis,0,sizeof(vis));//
15     dis[s]=0;vis[s]=1;
16     queue<int> qu;
17     qu.push(s);//出发点先入队
18     while (!qu.empty())
19     {
20         int head=qu.front();
21         qu.pop();//要记得pop！
22         vis[head]=0;
23         for (int i=1;i<=b[head][0];i++)//遍历和该点连接的所有边
24         {
25             if (dis[ b[head][i] ]>dis[head]+tu[head][ b[head][i] ])//
26             {
27                 dis[b[head][i]]=dis[head]+tu[head][b[head][i]];//更新最短距离
28                 if (vis[b[head][i]]==0)//如果该连接点不在队列里则入队
29                 {
30                     qu.push(b[head][i]);
31                     vis[b[head][i]]=1;
32                 }
33             }
34         }
35     }
36 }
37 int main()
38 {
39 //    freopen("in.txt","r",stdin);
40     int st,to,val;
41     cin>>n>>m;
42     for (int i=0;i<m;i++)
43     {
44         cin>>st>>to>>val;
45         b[st][0]++;b[st][b[st][0]]=to;tu[st][to]=val;//b[st][0]存以st为出发点的边数
46     }
47     spfa(1);//这里以1点为出发点
48     for (int i=2;i<=n;i++)
49     {
50         cout<<dis[i]<<endl;
51     }
52 
53     return 0;
54 }
55 
56 /*测试样例
57 5 7
58 0 4 10
59 0 1 2
60 1 4 7
61 3 4 5
62 4 2 6
63 1 2 3
64 2 3 4
65 */