首页 > > 程序设计 > C/C++ >

Folyd + 路径存储

2018-06-17 20:33:00来源：未知阅读 ()

一、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 }

View Code

上述代码中：存在重复存储，效率极低

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]);

View Code

优化代码：

由于上面代码每次都重复把点的信息都保存下来，因此，我们采用保存前驱几点的方式，最终通过回溯构建路径。

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 }

View Code

在更改权值的时候，即使记录下来当前点的前驱节点。 path[i][j] = path[k][j]; 切不可以写成，path[i][j] = k; 后者是另一种思路，下面会描述。path[i][j] = path[k][j] 达到 j 节点的前驱节点修改为经过k到j的路径上去。

完整代码：

测试数据：

View Code

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 }

View Code

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 }