SPFA以及各种优化

SPFA 算法是 Bellman-Ford算法的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 O(VE)。

判断负权边：其实就是多加一个 cnt[] 数组

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <stdbool.h>
 5 #include <stdlib.h>
 6 #include <string>
 7 #include <string.h>
 8 #include <math.h>
 9 #include <vector>
10 #include <queue>
11 #include <stack>
12 #include <set>
13 #include <map>
14 
15 #define INF 0x3f3f3f3f
16 #define LL long long
17 #define MAXN 1000005
18 #define mod 1000000007
19 using namespace std;
20 
21 vector<pair<int,int>> E[MAXN];
22 
23 int n,m;
24 int dis[MAXN],inq[MAXN];
25 int cnt[MAXN];
26 
27 void init()
28 {
29     for(int i=0;i<MAXN;i++)
30         E[i].clear();
31     for(int i=0;i<MAXN;i++)
32         inq[i] = 0;
33     for(int i=0;i<MAXN;i++)
34         dis[i] = 1e9;
35 }
36 
37 bool SPFA(int s)
38 {
39     queue<int> Q;
40     Q.push(s);
41     dis[s] = 0;
42     inq[s] = 1;
43     while (!Q.empty())
44     {
45         int now = Q.front();
46         Q.pop();
47         inq[now] = 0;
48         for (int i=0;i<E[now].size();i++)
49         {
50             int v = E[now][i].first;
51             if (dis[v]>dis[now]+E[now][i].second)
52             {
53                 dis[v] = dis[now]+E[now][i].second;
54                 if (inq[v]==1)
55                     continue;
56                 inq[v] = 1;
57                 cnt[v]++;
58                 Q.push(v);
59                 if (cnt[v]>m)
60                     return false;
61             }
62         }
63     }
64     return true;
65 }
66 
67 
68 int main()
69 {
70     while (cin >> n >> m)
71     {
72         init();
73         for (int i=0;i<m;i++)
74         {
75             int x,y,z;
76             cin >> x >> y >> z;
77             E[x].push_back(make_pair(y,z));
78             E[y].push_back(make_pair(x,z));
79         }
80         int s,t;
81         cin >> s >> t;
82         if(SPFA(s))
83             printf("No");
84         else
85             printf("Yes");
86     }
87     return 0;
88 }

最短路径：inq[] 防止重复访问

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <stdbool.h>
 5 #include <stdlib.h>
 6 #include <string>
 7 #include <string.h>
 8 #include <math.h>
 9 #include <vector>
10 #include <queue>
11 #include <stack>
12 #include <set>
13 #include <map>
14 
15 #define INF 0x3f3f3f3f
16 #define LL long long
17 #define MAXN 1000005
18 #define mod 1000000007
19 using namespace std;
20 
21 vector<pair<int,int>> E[MAXN];
22 
23 int n,m;
24 int dis[MAXN],inq[MAXN];
25 
26 void init()
27 {
28     for(int i=0;i<MAXN;i++)
29         E[i].clear();
30     for(int i=0;i<MAXN;i++)
31         inq[i] = 0;
32     for(int i=0;i<MAXN;i++)
33         dis[i] = 1e9;
34 }
35 
36 void SPFA(int s)
37 {
38     queue<int> Q;
39     Q.push(s);
40     dis[s] = 0;
41     inq[s] = 1;
42     while (!Q.empty())
43     {
44         int now = Q.front();
45         Q.pop();
46         inq[now] = 0;
47         for (int i=0;i<E[now].size();i++)
48         {
49             int v = E[now][i].first;
50             if (dis[v]>dis[now]+E[now][i].second)
51             {
52                 dis[v] = dis[now]+E[now][i].second;
53                 if (inq[v]==1)
54                     continue;
55                 inq[v] = 1;
56                 Q.push(v);
57             }
58         }
59     }
60 }
61 
62 
63 int main()
64 {
65     while (cin >> n >> m)
66     {
67         init();
68         for (int i=0;i<m;i++)
69         {
70             int x,y,z;
71             cin >> x >> y >> z;
72             E[x].push_back(make_pair(y,z));
73             E[y].push_back(make_pair(x,z));
74         }
75         int s,t;
76         cin >> s >> t;
77         SPFA(s);
78         if (dis[t] == 1e9)
79             printf("-1\n");
80         else
81             printf("%d\n",dis[t]);
82     }
83     return 0;
84 }

上面使用vector<pair<int,int> > 来写，现在用链表来写

其中edge[i].to表示第i条边的终点,edge[i].next表示与第i条边同起点的下一条边的存储位置,edge[i].w为边权值.

另外还有一个数组head[],它是用来表示以i为起点的第一条边存储的位置,实际上你会发现这里的第一条边存储的位置其实

在以i为起点的所有边的最后输入的那个编号.

更加具体的解释可以看博客：https://blog.csdn.net/ACdreamers/article/details/16902023

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <stdlib.h>
 5 #include <math.h>
 6 #include <stack>
 7 #include <queue>
 8 
 9 #define INF 0x3f3f3f3f
10 #define MAXN 10000
11 using namespace std;
12 
13 struct Edge{
14     int to;
15     int next;
16     int val;
17 }edge[MAXN*MAXN];
18 
19 int res,n;
20 int head[MAXN];
21 bool vis[MAXN];
22 int a[MAXN],dist[MAXN],cnt[MAXN];
23 
24 
25 void init(){
26     memset(head,-1, sizeof(head));
27     res = 0;
28 }
29 
30 void add(int u,int v,int w){
31     edge[res].to = v;
32     edge[res].val = w;
33     edge[res].next = head[u];
34     head[u] = res++;
35 }
36 
37 bool SPFA(int st){
38     memset(vis,false, sizeof(vis));
39     memset(cnt,0, sizeof(cnt));
40     for (int i=1;i<=n;i++)
41         dist[i] = INF;
42     dist[st] = 0;
43     queue<int> q;
44     q.push(st);
45     cnt[st] = 1;
46     vis[st] = true;
47     while (!q.empty())
48     {
49         int now = q.front();
50         q.pop();
51         vis[now] = false;
52         for (int i=head[now];i!=-1;i=edge[i].next)
53         {
54             int v = edge[i].to;
55             if (dist[v]>dist[now]+edge[i].val)
56             {
57                 dist[v] = dist[now]+edge[i].val;
58                 if (!vis[v])
59                 {
60                     vis[v] = true;
61                     q.push(v);
62                     cnt[v]++;
63                     if (cnt[v] > n)
64                        return false;  //负环
65                 }
66             }
67         }
68     }
69 }

有的题目queue的SPFA不给过，所以我们就要考虑deque双端队列的优化方法：

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 #include <set>
  8 #include <map>
  9 #include <string>
 10 #include <math.h>
 11 #include <stdlib.h>
 12 #include <time.h>
 13 using namespace std;
 14 
 15 #define INF 0x3f3f3f3f
 16 #define MAXN 100000
 17 #define LL long long
 18 using namespace std;
 19 
 20 struct Edge{
 21     int to;
 22     int next;
 23     int val;
 24 }edge[MAXN];
 25 
 26 
 27 int res;
 28 int cnt[MAXN];
 29 int head[MAXN];
 30 int dist[MAXN];
 31 bool vis[MAXN];
 32 
 33 void init()
 34 {
 35     memset(head,-1, sizeof(head));
 36     res = 0;
 37 }
 38 
 39 void add(int u,int v,int w)
 40 {
 41     edge[res].to = v;
 42     edge[res].val = w;
 43     edge[res].next = head[u];
 44     head[u] = res++;
 45 }
 46 
 47 bool SPFA(int n)
 48 {
 49     memset(vis,false,sizeof(vis));
 50     memset(cnt,0, sizeof(cnt));
 51     for (int i=1;i<=n;i++)
 52         dist[i]=INF;
 53     dist[1] = 0;
 54     vis[1] = true;
 55     cnt[1]++;
 56     deque<int > q;
 57     q.push_back(1);
 58     while (!q.empty())
 59     {
 60         int now = q.front();
 61         q.pop_front();
 62         vis[now] = false;
 63         for (int i=head[now];i!=-1;i=edge[i].next)
 64         {
 65             int v = edge[i].to;
 66             if (dist[v]>dist[now]+edge[i].val) {
 67                 dist[v] = dist[now] + edge[i].val;
 68                 if (!vis[v])
 69                 {
 70                     if (dist[v]<dist[q.front()] && !q.empty())
 71                         q.push_front(v);
 72                     else
 73                         q.push_back(v);
 74                     vis[v] = true;
 75                     if (++cnt[v]>n)
 76                         return false;
 77                 }
 78             }
 79         }
 80     }
 81     return true;
 82 }
 83 
 84 
 85 
 86 int main()
 87 {
 88     int n,m;
 89     while(~scanf("%d%d",&m,&n)) {
 90         init();
 91         for (int i = 1; i <= m; i++) {
 92             int u, v, w;
 93             scanf("%d%d%d", &u, &v, &w);
 94             add(u, v, w);
 95             add(v, u, w);
 96         }
 97         SPFA(n);
 98         printf("%d\n", dist[n]);
 99     }
100     return 0;
101 }