欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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 算法原理

  Folyd + 路径存储

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

  3. 记录路径,就是将 C 点连接在 B A C 这样的路径后  Folyd + 路径存储

     

二、简单容易理解版

核心代码:

Folyd + 路径存储
 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

 上述代码中:存在重复存储,效率极低

Folyd + 路径存储
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 如此逆推不难得到 最短路径记录值

核心代码:

Folyd + 路径存储
 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的路径上去。

 

完整代码:

测试数据:

Folyd + 路径存储
 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

 Folyd + 路径存储

 

 

1. 基础版本 

Folyd + 路径存储
 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. 改进版本

 

Folyd + 路径存储
 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