Folyd + 路径存储

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

新老客户大回馈,云服务器低至5折

一、Folyd 算法原理

  

  1. 如果 AB + AC < BC 那么, BC最短路就要经过 A。 在算法进行过程中,应该是 B-A 有很多路径,B 代表这些路径权值之和,A-C也有很多路径,C是这些权值之和。那么我们找到一个 满足  AB + AC < BC 的时候更新权值数组,并且记录路径。
  2. dist[i][j] = k 表示,从 I -- J 点的路径权值为 K

  3. 记录路径,就是将 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的路径上去。

 

完整代码:

测试数据:

 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
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 }
View Code

 

 

 

参考资料:

https://blog.csdn.net/start0609/article/details/7779042

https://blog.csdn.net/immiao/article/details/22199939

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Const 关键字详解

下一篇:OJ:奇怪的类复制