数据结构之最短路径(2) [弗洛伊德算法]

100 阅读 0 评论 66 点赞

我是靠谱客的博主靓丽小鸽子，这篇文章主要介绍数据结构之最短路径(2) [弗洛伊德算法]，现在分享给大家，希望可以做个参考。

【1】为什么需要弗洛伊德算法？

带权图中单个源点到所有顶点的最短路径问题可以用《迪杰斯特拉算法》求解。

那如果要求图中每一个顶点与其它顶点之间的最短路径呢？类似可以想到的方法为：

每次以一个顶点为源点，重复执行地杰斯特拉算法算法n次。

这样，理论上我们便可以求得每一个顶点与其它顶点的最短路径，总的执行时间为O(n3）。

好吧！为了实现这个中需求，可以采用另外一种求解算法：弗洛伊德算法。

为了更好的理解弗洛伊德算法的精妙，我们先看简单的案例。

如下图是一个最简单的3个顶点连通网图:

附上dist数组与prev数组：(左边为dist 右边为prev)

【2】弗洛伊德算法

弗洛伊德算法是非常漂亮的算法，简洁直观大气上档次。

不过很可惜由于它的三重循环，因此也是O(n*n*n)的时间复杂度。

如果你面临需要求所有顶点至所有顶点的最短路径问题？

它是很好的选择。

[如果上面的不太懂那就直接看代码就好啦，代码更容易懂一些]

代码如下：

复制代码

1 #include "stdafx.h"
 2 #include<iostream>
 3 #include<string>
 4 #define MAX_VERTEX_NUM 100
 5 #define INFINITY 65535
 6 typedef int Pathmatirx[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 7 typedef int ShortPathTable[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 8 using namespace std;
 9 typedef struct Graph
//有向图的邻接矩阵
10 {
11
char vexs[MAX_VERTEX_NUM];
//存放顶点的数组
12
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//定义一个临界矩阵
13
int vexnum, arcnum;
//总顶点数、总边数
14 }Graph;
15
16 int LocateVex(Graph G, char ch) //搜索
17 {
18
for (int i = 0; i < G.vexnum; i++)
19
if (G.vexs[i] == ch)
20
return i;
21
return -1;
22 }
23
24 void CreateGraph(Graph &G)
//创建无向图
25 {
26
char c1, c2;
//弧尾、弧头
27
int i, j, weight;
//weight为权重
28
cout << "请输入总顶点数、总边数(空格隔开):";
29
cin >> G.vexnum >> G.arcnum;
30
cout << "请输入顶点信息(空格隔开):" << endl;
31
for (i = 0; i < G.vexnum; i++)
32 
{
33
cin >> G.vexs[i];
34 
}
35
for (i = 0; i < G.vexnum; i++)
36
for (j = 0; j < G.vexnum; j++)
37
G.arcs[i][j] = INFINITY;
38
cout << "请输入弧尾、弧头以及权值:" << endl;
39
for (int k = 0; k < G.arcnum; k++)
40 
{
41
cin >> c1 >> c2 >> weight;
42
i = LocateVex(G, c1);
43
j = LocateVex(G, c2);
44
G.arcs[i][j] = weight;
45 
}
46 }
47
48 void ShortestPath_Floyd(Graph G, int prev[MAX_VERTEX_NUM][MAX_VERTEX_NUM], int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM])
49 {
//Floyd算法，求网图G中个顶点v到其余顶点w最短路径prev[v][w]及带权长度dist[v][w]
50
int v, w, k;
51
for (v = 0; v < G.vexnum; v++)
52
for (w = 0; w < G.vexnum; w++)
//初始化dist与prev
53 
{
54
dist[v][w] = G.arcs[v][w];
//dist[v][w]值即为对应点间的权值
55
prev[v][w] = w;
//初始化prev
56 
}
57
for (k = 0; k < G.vexnum; k++)
//更新路径
58
for (v = 0; v < G.vexnum; v++)
59
for (w = 0; w < G.vexnum; w++)
60
{
//如果经过下标为k顶点路径比原两点间路径更短
61
if (dist[v][w] > dist[v][k] + dist[k][w])
62 
{
63
dist[v][w] = dist[v][k] + dist[k][w];
64
prev[v][w] = prev[v][k];
//路径设置经过下标为k的顶点
65 
}
66 
}
67
for (v = 0; v < G.vexnum; v++)
//输出函数
68 
{
69
for (w = v + 1; w < G.vexnum; w++)
70 
{
71
cout << G.vexs[v] << " - " << G.vexs[w] << " weight: " << dist[v][w]<<" ";
72
int k = prev[v][w];
73
cout << "path: " << G.vexs[v];
74
while (k != w)
75 
{
76
cout << "->" << G.vexs[k];
77
k = prev[k][w];
78 
}
79
cout << "->" << G.vexs[w]<<" ";
80 
}
81
cout << endl;
82 
}
83 }
84
85 int main()
86 {
87 
Graph G;
88
int prev[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
89
int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
90
int v0;
91 
CreateGraph(G);
92 
ShortestPath_Floyd(G, prev, dist);
93
94 }

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
 1 #include "stdafx.h"
 2 #include<iostream>
 3 #include<string>
 4 #define MAX_VERTEX_NUM 100
 5 #define INFINITY 65535
 6 typedef int Pathmatirx[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 7 typedef int ShortPathTable[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 8 using namespace std;
 9 typedef struct Graph
//有向图的邻接矩阵
10 {
11
char vexs[MAX_VERTEX_NUM];
//存放顶点的数组
12
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//定义一个临界矩阵
13
int vexnum, arcnum;
//总顶点数、总边数
14 }Graph;
15
16 int LocateVex(Graph G, char ch) //搜索
17 {
18
for (int i = 0; i < G.vexnum; i++)
19
if (G.vexs[i] == ch)
20
return i;
21
return -1;
22 }
23
24 void CreateGraph(Graph &G)
//创建无向图
25 {
26
char c1, c2;
//弧尾、弧头
27
int i, j, weight;
//weight为权重
28
cout << "请输入总顶点数、总边数(空格隔开):";
29
cin >> G.vexnum >> G.arcnum;
30
cout << "请输入顶点信息(空格隔开):" << endl;
31
for (i = 0; i < G.vexnum; i++)
32 
{
33
cin >> G.vexs[i];
34 
}
35
for (i = 0; i < G.vexnum; i++)
36
for (j = 0; j < G.vexnum; j++)
37
G.arcs[i][j] = INFINITY;
38
cout << "请输入弧尾、弧头以及权值:" << endl;
39
for (int k = 0; k < G.arcnum; k++)
40 
{
41
cin >> c1 >> c2 >> weight;
42
i = LocateVex(G, c1);
43
j = LocateVex(G, c2);
44
G.arcs[i][j] = weight;
45 
}
46 }
47
48 void ShortestPath_Floyd(Graph G, int prev[MAX_VERTEX_NUM][MAX_VERTEX_NUM], int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM])
49 {
//Floyd算法，求网图G中个顶点v到其余顶点w最短路径prev[v][w]及带权长度dist[v][w]
50
int v, w, k;
51
for (v = 0; v < G.vexnum; v++)
52
for (w = 0; w < G.vexnum; w++)
//初始化dist与prev
53 
{
54
dist[v][w] = G.arcs[v][w];
//dist[v][w]值即为对应点间的权值
55
prev[v][w] = w;
//初始化prev
56 
}
57
for (k = 0; k < G.vexnum; k++)
//更新路径
58
for (v = 0; v < G.vexnum; v++)
59
for (w = 0; w < G.vexnum; w++)
60
{
//如果经过下标为k顶点路径比原两点间路径更短
61
if (dist[v][w] > dist[v][k] + dist[k][w])
62 
{
63
dist[v][w] = dist[v][k] + dist[k][w];
64
prev[v][w] = prev[v][k];
//路径设置经过下标为k的顶点
65 
}
66 
}
67
for (v = 0; v < G.vexnum; v++)
//输出函数
68 
{
69
for (w = v + 1; w < G.vexnum; w++)
70 
{
71
cout << G.vexs[v] << " - " << G.vexs[w] << " weight: " << dist[v][w]<<" ";
72
int k = prev[v][w];
73
cout << "path: " << G.vexs[v];
74
while (k != w)
75 
{
76
cout << "->" << G.vexs[k];
77
k = prev[k][w];
78 
}
79
cout << "->" << G.vexs[w]<<" ";
80 
}
81
cout << endl;
82 
}
83 }
84
85 int main()
86 {
87 
Graph G;
88
int prev[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
89
int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
90
int v0;
91 
CreateGraph(G);
92 
ShortestPath_Floyd(G, prev, dist);
93
94 }