四种常用最短路径算法模板
四种常用最短路径算法模板
forrestlin
发布于 2022-04-02 10:20:00
发布于 2022-04-02 10:20:00
代码可运行
运行总次数：0
代码可运行
转自：http://www.cnblogs.com/genyuan/archive/2013/05/01/3053904.html
最短路径算法中，有四种算法是最常见的，分别是Dijkstra算法，Floyd算法，Bellman-Ford算法和SPFA算法。
Dijkstra算法，求单源最短路径最稳定的一个算法，算法复杂度为O（n2），但可以通过队列优化。下面列出的模板是最原始的Dijkstra算法。以需要求的源为中心，向四周扩散，第一次求出的是与源直接相连接的点的距离。求出这些距离中的最短距离，然后通过这个点将与它相连接的点的最短距离更新，然后再求出现在的最短距离，如此这样下去，直到所有的点都已经被遍历过为止。已经求出最短距离的点不在参与更新。具体模板如下(以POJ3268为例）:
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <cstdlib>
6 #include <algorithm>
7 #include <queue>
8 #include <vector>
9 #include <map>
10 using namespace std;
11 #define INF 0x7ffffff
12 #define eps 1e-8
13 #define sgn(a) (a>eps)-(a<-eps)
14 #define LL long long
15 #define out(v) cerr << #v << ": " << (v) << endl
16 #define SZ(v) ((int)(v).size())
17 const int maxint = -1u>>1;20 int n,m,x;
21 const int maxn = 1111;
22 int dist[maxn];
23 int dist2[maxn];
24 int d[maxn][maxn];
25 bool flag[maxn];
26
27 void Dijkstra(int x)
28 {
29 memset(flag,false,sizeof(flag));
30 for(int i=1;i<=n;++i)
31 {
32 dist[i] = d[x][i];
33 }
34 flag[x] = true;
35 dist[x] = 0;
36
37 for(int i=2;i<=n;++i)
38 {
39 //寻找没有标记而且dist值最小的点
40 int u = 1;
41 int mindis = maxint;
42 for(int j=1;j<=n;++j)
43 {
44 if(!flag[j] && dist[j] < mindis)
45 {
46 mindis = dist[j];
47 u = j;
48 }
49 }
50 flag[u] = true;
51 for(int j=1;j<=n;++j)
52 {
53 if(!flag[j] && d[u][j] < maxint)
54 {
55 dist[j] = min(dist[j],dist[u] + d[u][j]);
56 }
57 }
58 }
59 }
60
61
62 int main()
63 {
64 while(scanf("%d%d%d",&n,&m,&x) != EOF)
65 {
66 int a,b,len;
67 for(int i=1;i<=n;++i)
68 {
69 for(int j=1;j<=n;++j)
70 {
71 d[i][j] = maxint;
72 }
73 }
74 for(int i=1;i<=m;++i)
75 {
76 scanf("%d%d%d",&a,&b,&len);
77 d[a][b] = len;
78 }
79 Dijkstra(x);
80 for(int i=1;i<=n;++i) dist2[i] = dist[i];
81 for(int i=1;i<=n;++i)
82 {
83 for(int j=i+1;j<=n;++j)
84 {
85 swap(d[i][j],d[j][i]);
86 }
87 }
88 Dijkstra(x);
89 int ans = 0;
90 for(int i=1;i<=n;++i)
91 {
92 ans = max(ans,dist[i] + dist2[i]);
93 }
94 printf("%d\n",ans);
95 }
96 return 0;
97 }Floyd算法其实是Floyd-Warshall算法的简称。分以下两步进行。
1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
Floyd算法是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。
具体模板如下所示（以POJ2240为例）:
1 /*
2 * Author: xiagenyuan
3 * Created Time: 2013/5/1 21:03:44
4 * File Name: D:\ACMICPC\20130501\POJ2240.cpp
5 */
6 #include <iostream>
7 #include <cstdio>
8 #include <cstring>
9 #include <cmath>
10 #include <string>
11 #include <algorithm>
12 #include <queue>
13 #include <vector>
14 #include <map>
15 using namespace std;
16 #define eps 1e-8
17 #define sgn(a) (a>eps)-(a<-eps)
18 #define LL long long
19 const int maxint = -1u>>1;
20 const int maxn = 33;
21 int n,m;
22 map<string,int> mp;//用来为名字是字符串的点对应数字
23 double ra[maxn][maxn]; //存取两点间的的路径
24
25 void Floyd()//对临接表进行Floyd处理
26 {
27 for(int k=1;k<=n;++k)
28 {
29 for(int i=1;i<=n;++i)
30 {
31 for(int j=1;j<=n;++j)
32 {
33 if(ra[i][j] < ra[i][k]*ra[k][j])
34 {
35 ra[i][j] = ra[i][k]*ra[k][j];
36 }
37 }
38 }
39 }
40 }
41
42 int main()
43 {
44 int cas = 1;
45 while(scanf("%d",&n) != EOF && n)
46 {
47 mp.clear();
48 string name;
49 for(int i=1;i<=n;++i)
50 {
51 cin>>name;
52 mp[name]=i;
53 }
54 scanf("%d",&m);
55 string name1,name2;
56 double rate;
57 memset(ra,1,sizeof(ra));
58 for(int i=1;i<=m;++i)
59 {
60 cin>>name1>>rate>>name2;
61 ra[mp[name1]][mp[name2]]= rate;
62 }
63 Floyd();
64 bool flag = false;
65 for(int i=1;i<=n;++i)
66 {
67 if(ra[i][i] > 1)
68 {
69 flag = true;
70 break;
71 }
72 }
73 if(flag) printf("Case %d: Yes\n",cas);
74 else printf("Case %d: No\n",cas);
75 cas++;
76 }
77 return 0;
78 }Bellman-Ford算法
1、以下操作循环执行至多n-1次，n为顶点数： 2、对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值； 若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；
3、为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。
具体模板如下所示：
1 /*
2 * Author: xiagenyuan
3 * Created Time: 2013/5/1 21:39:36
4 * File Name: C:\Users\Genyuan\Desktop\图论系列模板\Bellman-Ford.cpp
5 */
6 //模板未进行验证
7 #include <iostream>
8 #include <cstdio>
9 #include <cstring>
10 #include <cmath>
11 #include <string>
12 #include <algorithm>
13 #include <queue>
14 #include <vector>
15 #include <map>
16 using namespace std;
17 #define eps 1e-8
18 #define sgn(a) (a>eps)-(a<-eps)
19 #define LL long long
20 const int maxint = 9999999;
21 const int maxnum = 100;
22 struct edge
23 {
24 int u,v;//每条边的起点和终点
25 int weight;//边的权值
26 };
27 edge e[maxnum];//保存所有边的值
28 int dist[maxnum]; //保存节点到源点的最短距离
29 int n,m,x; //节点数量，边的数量，源点
30
31 //读入数据，初始化图
32 void init()
33 {
34 while(scanf("%d%d%d",&n,&m,&x) != EOF)
35 {
36 for(int i=1;i<=n;++i) dist[i] = maxint;
37 dist[x] = 0;
38 for(int i=1;i<m;++i)
39 {
40 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].weight);
41 if(e[i].u == x) dist[e[i].v] = e[i].weight;
42 }
43 }
44 }
45 //松弛计算
46 void relax(int u,int v,int weight)
47 {
48 dist[v] = min(dist[v],dist[u]+weight);
49 }
50
51 bool BellmanFord()
52 {
53 for(int i=1;i<n-1;++i)
54 {
55 for(int j=1;j<=m;++j)
56 {
57 relax(e[j].u,e[j].v,e[j].weight);
58 }
59 }
60 bool flag = true;
61 for(int i=1;i<m;++i)
62 {
63 if(dist[e[i].v] > dist[e[i].u]+e[i].weight)
64 {
65 flag = false;
66 break;
67 }
68 }
69 return flag;
70 }
71
72 int main()
73 {
74 init();
75 if(BellmanFord())
76 {
77 for(int i=1;i<=m;++i) cout<<dist[i]<<" ";
78 cout<<endl;
79 }
80 else cout<<"No"<<endl;
81 return 0;
82 }SPFA算法其实就是Bellman-Ford算法，只是它用队列进行了优化。用队列进行优化有三种形式：
1、简单地用队列进行存储。
2、SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾。
3、LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i
出对进行松弛操作。
以下模板是针对第一种情况（POJ3268为例）：
1 /*
2 * Author: xiagenyuan
3 * Created Time: 2013/5/1 22:26:23
4 * File Name: D:\ACMICPC\20130501\POJ3268SPFA.cpp
5 */
6 #include <iostream>
7 #include <cstdio>
8 #include <cstring>
9 #include <cmath>
10 #include <string>
11 #include <algorithm>
12 #include <queue>
13 #include <vector>
14 #include <map>
15 using namespace std;
16 #define eps 1e-8
17 #define sgn(a) (a>eps)-(a<-eps)
18 #define LL long long
19 const int maxint = 99999999;
20 const int maxn = 1000 + 111;
21 int n,m,x;
22 int d[maxn][maxn];
23 int dist[maxn];
24 int dist2[maxn];
25 bool visited[maxn];
26 int que[2*maxn];
27
28 void spfa()
29 {
30 int pri = 0,end = 1;
31 memset(visited,false,sizeof(visited));
32 visited[x] = true;
33 for(int i=1;i<=n;++i) dist[i] = maxint;
34 dist[x] = 0;
35 que[0] = x;
36 while(pri < end)
37 {
38 int index = que[pri];
39 for(int i=1;i<=n;++i)
40 {
41 if(dist[index] + d[index][i] < dist[i])
42 {
43 dist[i] = dist[index] + d[index][i];
44 if(!visited[i])
45 {
46 que[end++] = i;
47 visited[i] = true;
48 }
49 }
50 }
51 visited[index] = false;
52 pri++;
53 }
54 }
55
56 int main()
57 {
58 while(scanf("%d%d%d",&n,&m,&x) != EOF)
59 {
60 int a,b,len;
61 for(int i=1;i<=n;++i)
62 {
63 for(int j=1;j<=n;++j)
64 {
65 d[i][j] = maxint;
66 }
67 }
68 for(int i=1;i<=m;++i)
69 {
70 scanf("%d%d%d",&a,&b,&len);
71 d[a][b] = len;
72 }
73 spfa();
74 for(int i=1;i<=n;++i) dist2[i] = dist[i];
75 for(int i=1;i<=n;++i)
76 {
77 for(int j=i+1;j<=n;++j)
78 {
79 swap(d[i][j],d[j][i]);
80 }
81 }
82 spfa();
83 int ans = 0;
84 for(int i=1;i<=n;++i)
85 {
86 ans = max(ans,dist[i] + dist2[i]);
87 }
88 printf("%d\n",ans);
89 }
90 return 0;
91 }本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
