Floyd算法是多源最短路算法，复杂度最高（n^3），通常用在点比较少的起点不固定的问题中。能解决负边（负权）但不能解决负环。
Dijkstra算法是单源最短路算法，最常用时间复杂度（n^2）优化后可以达到（nlogn），不能解决负边问题，稀疏图（点的范围很大但是边不多，边的条数|E|远小于|V|²）需要耗费比较多的空间。
算法和 Dijkstra 算法同为解决单源最短路径的算法。对于带权有向图 G = (V, E)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford 算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。
SPFA算法适合稀疏图，可以解决带有负权边，负环的问题，但是在稠密图中效率比Dijkstra要低。
Floyd：
核心代码只有几行：
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
}
}
}
可以找多源最短路，时间复杂度高。
下面是完整代码：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#include <iostream> #include <cstring> #include <algorithm> #define inf 0x3f3f3f3f const int maxn = 105; int map[maxn][maxn]; using namespace std; int main() { int n, m, a, b, c, str, end; //点，边，路径与权，开始坐标，结尾坐标 cin >> n >> m; for (int i = 1; i <= n; i++){ //图的初始化，对角线（即本身到本身）为0，其余为无穷 for (int j = 1; j <= n; j++){ if (i == j) map[i][j] = 0; else map[i][j] = inf; } } for (int i = 1; i <= m; i++){ //记录路径 cin >> a >> b >> c; if (map[a][b] > c){ //重复输入保存最小值 map[a][b] = map[b][a] = c; } } cin >>str >> end; //开始，结尾坐标 for (int k = 1; k <= n; k++){ //k在最外层 for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ map[i][j] = min(map[i][j], map[i][k] + map[k][j]); } } } cout << map[str][end] << endl; return 0; }
Dijkstra：
只能计算单元最短路，不能计算负权值，贪心思想。开一个dis数组用来存储起始点到其他点的最短路，初始化时存的是起始点到其它点的初始路程，通过n-1遍的遍历找最短。例如1到3的最短路就是比较dis[3]与dis[2]+map[2][3]的值。另外开辟一个book数组用来标记已经找过的最短路。
下面是完整代码：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58#include <iostream> #include <cstring> #include <algorithm> #define inf 0x3f3f3f3f const int maxn = 105; int map[maxn][maxn], dis[maxn], book[maxn]; //图，最短路，记录 using namespace std; int main() { memset(book, 0, sizeof(book)); int n, m, a, b, c, u, v, Min; //点，边，路径和权，Min下面求最短路用 cin >> n >> m; for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ if (i == j) map[i][j] = 0; //图的初始化 else map[i][j] = inf; } } for (int i = 1; i <= m; i++){ cin >> a >> b >> c; if (map[a][b] > c){ map[a][b] = map[b][a] = c; } } for (int i = 1; i <= n; i++){ //距离初始为到i的权 dis[i] = map[1][i]; } book[1] = 1; //1到1默认走过 for (int i = 1; i < n; i++){ Min = inf; //Min初始为无穷大 for (int j = 1; j <= n; j++){ if (book[j] == 0 && dis[j] < Min){ //判断是否标记以及是否可走（不可走为无穷） Min = dis[j]; book[j] = 1; u = j; } } for (int v = 1; v <= n; v++){ //求最短路 if (map[u][v] < inf){ dis[v] = min(dis[v], dis[u] + map[u][v]); } } } for (int i = 1; i <= n; i++){ //输出每个最短路 cout << dis[i] << " "; } return 0; }
Bellman-Ford：
怎样判断负权回路？
当进行n-1次循环之后，仍然可以运行核心代码部分交换值（if判断语句内的内容）则一定形成负权回路。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71#include <iostream> #include <cstring> #include <algorithm> #define inf 0x3f3f3f3f using namespace std; const int MAX=105; int u[MAX],v[MAX],w[MAX],dis[MAX]; int main() { int n,m,check,flag; //顶点个数，边数 ,检验是否可以退出循环，负权回路判断 cin>>n>>m; for(int i=1;i<=m;i++) //读入边 { cin>>u[i]>>v[i]>>w[i]; } for(int i=1;i<=n;i++) //1号点到各个点的初始位置设为无穷 { dis[i]=inf; } dis[1]=0; for(int k=1;k<=n-1;k++) //Bellman-Ford算法核心 { check=0; for(int i=1;i<=m;i++) { if(dis[v[i]]>dis[u[i]]+w[i]) { dis[v[i]]=dis[u[i]]+w[i]; check=1; } } if(check==0) //若不再更新则可以退出 { break; } } flag=0; for(int i=1;i<=m;i++) //判断负权回路 { if(dis[v[i]]>dis[u[i]]+w[i]) { flag=1; } } if(flag==1) { cout<<"存在负权回路"<<endl; } else { cout<<"不存在负权回路"<<endl; } for(int i=1;i<=n;i++) //输出1到各点距离 { cout<<dis[i]<<" "; } return 0; } /*5 5 2 3 2 1 2 -3 1 5 5 4 5 2 3 4 3*/
Spfa（Bellman-Ford的队列优化）：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82#include <iostream> #include <cstring> #include <algorithm> #define inf 0x3f3f3f3f using namespace std; const int MAX=1e3+5; int u[MAX],v[MAX],w[MAX],first[MAX],next[MAX],dis[MAX],book[MAX]; //起始，终止，权，此值的最后一条边的存储位置，此值的上一条边的存储位置，距离，记录 int main() { int n,m; //点，边 cin>>n>>m; memset(dis,0x3f,sizeof(dis)); //距离初始无穷 dis[1]=0; //1-1初始为0 memset(book,0,sizeof(book)); //清空记录数组 for(int i=1;i<=n;i++) //初始-1 { first[i]=-1; } for(int i=1;i<=m;i++) //读入图 { cin>>u[i]>>v[i]>>w[i]; next[i]=first[u[i]]; //链式前向星 first[u[i]]=i; } int que[MAX]={0},head=1,tail=1,k; //队列，头，尾 que[tail]=1,tail++; //1号顶点入队 book[1]=1; //入队标记 while(head<tail) //队列不为空的时候循环 { k=first[que[head]]; //当前需要处理的首顶点 while(k!=-1) //扫描当前所有的边 { if(dis[v[k]]>dis[u[k]]+w[k]) //判断是否松弛 { dis[v[k]]=dis[u[k]]+w[k]; //更新值 if(book[v[k]]==0) //用数组记录顶点v[k]是否在队列中，不然每次都要从head-tail扫一遍 { que[tail]=v[k]; //入队 tail++; book[v[k]]=1; } } k=next[k]; } book[que[head]]=0; //出队 head++; } for(int i=1;i<=n;i++) //输出所有1-i的最短距离 { cout<<dis[i]<<" "; } return 0; } /* 5 7 1 2 2 1 5 10 2 3 3 2 5 7 3 4 4 4 5 5 5 3 6 0 2 5 9 9 */
queue实现：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82#include <iostream> #include <cstring> #include <queue> #include <algorithm> #define inf 0x3f3f3f3f using namespace std; const int MAX=1e3+5; struct point { int to,next,d; }; point a[MAX]; int head[MAX]; int main() { int n,m,x,y,d; cin>>n>>m; int cnt=0; memset(head,0,sizeof(head)); for(int i=1;i<=m;i++) //存图 { cin>>x>>y>>d; a[++cnt].next=head[x]; a[cnt].to=y; a[cnt].d=d; head[x]=cnt; a[++cnt].next=head[y]; a[cnt].to=x; a[cnt].d=d; head[y]=cnt; } int v0=1; //这里是从1，不是head[1] int book[MAX],dis[MAX]; memset(book,0,sizeof(book)); memset(dis,0x3f,sizeof(dis)); book[v0]=1; queue<int>q; q.push(v0); dis[v0]=0; while(!q.empty()) //非空循环 { int u=q.front(); //当前需要处理的元素 q.pop(); //出队 book[u]=0; for(int i=head[u];i;i=a[i].next) { int v=a[i].to; if(dis[v]>dis[u]+a[i].d) //松弛 { dis[v]=dis[u]+a[i].d; if(book[v]==0) { q.push(v); //进队 book[v]=1; } } } } for(int i=1;i<=n;i++) //输出所有1-i的最短距离 { cout<<dis[i]<<" "; } return 0; } /* 5 7 1 2 2 1 5 10 2 3 3 2 5 7 3 4 4 4 5 5 5 3 6 0 2 5 9 9 */
最后
以上就是激昂蜜粉最近收集整理的关于ACM寒假集训第三四五天：最短路（Dijkstra、Bellman-Ford、SPFA、Floyd） 基础建图模型的全部内容，更多相关ACM寒假集训第三四五天：最短路（Dijkstra、Bellman-Ford、SPFA、Floyd）内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复