Folyd + 路径存储

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