Folyd + 路径存储
程序员文章站
2022-04-04 16:40:09
一、Folyd 算法原理 dist[i][j] = k 表示，从 I -- J 点的路径权值为 K 记录路径，就是将 C 点连接在 B A C 这样的路径后 二、简单容易理解版 核心代码： 1 //邻接矩阵保存点信息 2 int mapp[MAX_POINT][MAX_POINT]; 3 //保存任 ......
一、Folyd 算法原理
- 如果 AB + AC < BC 那么， BC最短路就要经过 A。 在算法进行过程中，应该是
，B-A 有很多路径，B 代表这些路径权值之和，A-C也有很多路径，C是这些权值之和。那么我们找到一个 满足 AB + AC < BC 的时候更新权值数组，并且记录路径。
-
dist[i][j] = k 表示，从 I -- J 点的路径权值为 K
-
记录路径，就是将 C 点连接在 B A C 这样的路径后
二、简单容易理解版
核心代码：
1 //邻接矩阵保存点信息
2 int mapp[MAX_POINT][MAX_POINT];
3 //保存任意两点之间的最短路径上的节点
4 vector<int> trace_path[MAX_POINT][MAX_POINT];
5
6 void Folyd(int n) {
7 for (int k = 0; k < n; k++)
8 for (int i = 0; i < n; i++)
9 for (int j = 0; j < n; j++)
10 if (mapp[i][j] > mapp[i][k] + mapp[k][j]) {
11 mapp[i][j] = mapp[i][k] + mapp[k][j];
12 trace_path[i][j].clear();
13 //放入 i---k 路径节点
14 for (int z = 0; z < trace_path[i][k].size(); z++)
15 trace_path[i][j].push_back(trace_path[i][k][z]);
16 //放入 k---j 路径节点
17 for (int z = 0; z < trace_path[k][j].size(); z++)
18 trace_path[i][j].push_back(trace_path[k][j][z]);
19 }
20 }
21
22 void query(int from, int to) {
23 cout << "from " << from << " to " << to << " should cost " << mapp[from][to] <<"."<< endl;
24 cout << "trace_path: " ;
25 for (int i = 0; i < trace_path[from][to].size(); i++)
26 cout<< trace_path[from][to][i] << " -> ";
27 cout << to << endl;
28 }
上述代码中：存在重复存储，效率极低
1 trace_path[i][j].clear(); 2 //放入 i---k 路径节点 3 for (int z = 0; z < trace_path[i][k].size(); z++) 4 trace_path[i][j].push_back(trace_path[i][k][z]); 5 //放入 k---j 路径节点 6 for (int z = 0; z < trace_path[k][j].size(); z++) 7 trace_path[i][j].push_back(trace_path[k][j][z]);
优化代码：
由于上面代码每次都重复把点的信息都保存下来，因此，我们采用保存前驱几点的方式，最终通过回溯构建路径。
path[i][j] = k ; //表示 从 i---j 路径中， k 是 j 的直接前驱， 那么最短路径 1->5->4->3->6 有 paht[1][6] = 3; paht[1][3]= 4; paht[1][4] = 5; paht[1][5] =1 如此逆推不难得到 最短路径记录值
核心代码：
1 //邻接矩阵保存点信息
2 int mapp[MAX_POINT][MAX_POINT];
3 //path[i][j] = k ,表示从 i 到 j 最短路， k 邻接到j。
4 int path[MAX_POINT][MAX_POINT];
5 void Folyd(int n) {
6 //初始化路径数组
7 for (int i = 0; i < n; i++)
8 for (int j = 0; j < n; j++) {
9 if (mapp[i][j] - INF)
10 path[i][j] = i;
11 else
12 path[i][j] = NOTEXISTS;
13 }
14
15 for (int k = 0; k < n; k++)
16 for (int i = 0; i < n; i++)
17 for (int j = 0; j < n; j++)
18 if (mapp[i][j] > mapp[i][k] + mapp[k][j]) {
19 mapp[i][j] = mapp[i][k] + mapp[k][j];
20 //path[i][j] = k; //这种思路中，不能写成这样
21 path[i][j] = path[k][j];
22 }
23 }
24
25 void print_path(int from, int to) {
26 if (path[from][to] != from)
27 print_path(from, path[from][to]);
28 cout << " -> " << to;
29 }
在更改权值的时候，即使记录下来当前点的前驱节点。 path[i][j] = path[k][j]; 切不可以写成，path[i][j] = k; 后者是另一种思路，下面会描述。path[i][j] = path[k][j] 达到 j 节点 的前驱节点修改为经过k到j的路径上去。
完整代码：
测试数据：
1 8 2 0 5 2 3 0 3 4 4 0 4 1 5 1 5 8 6 1 3 3 7 2 4 6 8 2 6 3 9 1 7 2 10 -1 0 0
1. 基础版本
1 //Folyd
2 #include <iostream>
3 #include <vector>
4 #include <algorithm>
5
6 using namespace std;
7
8 const int INF = 0x3f3f3f3f;
9 const int MAX_POINT = 10;
10
11 //邻接矩阵保存点信息
12 int mapp[MAX_POINT][MAX_POINT];
13 //保存任意两点之间的最短路径上的节点
14 vector<int> trace_path[MAX_POINT][MAX_POINT];
15
16 void Folyd(int n) {
17 for (int k = 0; k < n; k++)
18 for (int i = 0; i < n; i++)
19 for (int j = 0; j < n; j++)
20 if (mapp[i][j] > mapp[i][k] + mapp[k][j]) {
21 mapp[i][j] = mapp[i][k] + mapp[k][j];
22 trace_path[i][j].clear();
23 //放入 i---k 路径节点
24 for (int z = 0; z < trace_path[i][k].size(); z++)
25 trace_path[i][j].push_back(trace_path[i][k][z]);
26 //放入 k---j 路径节点
27 for (int z = 0; z < trace_path[k][j].size(); z++)
28 trace_path[i][j].push_back(trace_path[k][j][z]);
29 }
30 }
31
32 void query(int from, int to) {
33 cout << "from " << from << " to " << to << " should cost " << mapp[from][to] <<"."<< endl;
34 cout << "trace_path: " ;
35 for (int i = 0; i < trace_path[from][to].size(); i++)
36 cout<< trace_path[from][to][i] << " -> ";
37 cout << to << endl;
38 }
39
40 int main(int argc, char const *argv[])
41 {
42 int n;
43 cout << "Please input gragh points:";
44 cin >> n;
45 //init container， 自己到自己默认 0，其他为 INF
46 for (int i = 0; i < n; i++) {
47 mapp[i][i] = 0;
48 for (int j = 0; j < n; j++)
49 if (i != j)
50 mapp[i][j] = INF;
51 }
52
53
54 int t = (n*(n - 1)) >> 1;
55 // 最多输入 n(n -1)>>1 条边
56 cout << "Please input edges format a tuple (f, t , v), to end input via (-1, 0, 0)" << endl;
57 while (--t > 0) {
58 int from, to, value;
59 cin >> from >> to >> value;
60 if (~from) {
61 //无向图
62 mapp[from][to] = value;
63 mapp[to][from] = value;
64 //每条路的前驱放入路径中
65 trace_path[from][to].push_back(from);
66 trace_path[to][from].push_back(to);
67 }
68 else
69 break;
70 }
71
72 Folyd(n);
73
74 //结果打表
75 cout << "====================" << endl;
76 for (int i = 0; i < n; i++) {
77
78 for (int j = 0; j < n; j++)
79 cout << mapp[i][j] << "\t";
80 cout << endl;
81 }
82 cout << "====================" << endl;
83 while(1){
84 int beginP, endP;
85 cout << "Please input begin point and end point:";
86 cin >> beginP >> endP;
87 query(beginP, endP);
88 }
89 return 0;
90 }
2. 改进版本
1 //Folyd
2 //输入图,可以不连通
3 #include <iostream>
4 using namespace std;
5
6 const int INF = 0x3f3f3f3f;
7 const int MAX_POINT = 10;
8 const int NOTEXISTS = ~(0U);
9
10 //邻接矩阵保存点信息
11 int mapp[MAX_POINT][MAX_POINT];
12 //path[i][j] = k ,表示从 i 到 j 最短路， k 邻接到j。
13 int path[MAX_POINT][MAX_POINT];
14 void Folyd(int n) {
15 //初始化路径数组
16 for (int i = 0; i < n; i++)
17 for (int j = 0; j < n; j++) {
18 if (mapp[i][j] - INF)
19 path[i][j] = i;
20 else
21 path[i][j] = NOTEXISTS;
22 }
23
24 for (int k = 0; k < n; k++)
25 for (int i = 0; i < n; i++)
26 for (int j = 0; j < n; j++)
27 if (mapp[i][j] > mapp[i][k] + mapp[k][j]) {
28 mapp[i][j] = mapp[i][k] + mapp[k][j];
29 path[i][j] = path[k][j];
30 }
31 }
32
33 void print_path(int from, int to) {
34 if (path[from][to] != from)
35 print_path(from, path[from][to]);
36 cout << " -> " << to;
37 }
38
39 int main(int argc, char const *argv[])
40 {
41 int n;
42 cout << "Please input gragh points:";
43 cin >> n;
44
45 //init container
46 for (int i = 0; i < n; i++) {
47 mapp[i][i] = 0; //自己到自己默认 0
48 for (int j = 0; j < n; j++)
49 if (i != j)
50 mapp[i][j] = INF;
51 }
52
53 int t = (n*(n - 1)) >> 1;
54 // 最多输入 n(n -1)>>1 条边
55 cout << "Please input edges format a tuple (f, t , v), to end input via (-1, 0, 0)" << endl;
56 while (--t > 0) {
57 int from, to, value;
58 cin >> from >> to >> value;
59 if (~from) {
60 mapp[from][to] = value;
61 mapp[to][from] = value;
62 }
63 else
64 break;
65 }
66 Folyd(n);
67
68 cout << "====================" << endl;
69 for (int i = 0; i < n; i++) {
70
71 for (int j = 0; j < n; j++)
72 cout << mapp[i][j] << "\t";
73 cout << endl;
74 }
75 cout << "====================" << endl;
76 while (1) {
77 int beginP, endP;
78 cout << "Please input begin point and end point:";
79 cin >> beginP >> endP;
80 //print path
81 cout << "from " << beginP << " to " << endP << " should cost " << mapp[beginP][endP] << "." << endl;
82 if (path[beginP][endP] == NOTEXISTS)
83 cout << "No path!" << endl;
84 else {
85 cout << "trace_path: ";
86 cout << beginP;
87 print_path(beginP, endP);
88 cout << endl;
89 }
90 }
91 return 0;
92 }
参考资料：
https://blog.csdn.net/start0609/article/details/7779042
https://blog.csdn.net/immiao/article/details/22199939