Floyd(动态规划)求解任意两点间的最短路径(图解)

Floyd算法的精髓在于动态规划的思想,即每次找最优解时都建立在上一次最优解的基础上,当算法执行完毕时一定是最优解

对于邻接矩阵w,w保存最初始情况下任意两点间的直接最短距离,但没有加入中继点进行考虑
如w[1][2]=20,即表示点1与点2的当前最短距离(直接距离)为20

对于路径矩阵path,保存了点i到点j的最短路径中下一个点的位置,
如path[1][2]=0,表示1->2的路径中的下一个点为结点0

Floyd算法对所有中继点在任意两点中进行循环遍历.即k从0-n时考虑(i->k,k->j)的路径是否小于(i->j)的路,如果小于即更新邻接矩阵w的值与path矩阵中的值,使其始终保持最短
图解如下:

代码用例:

代码如下

#include<iostream> #include<fstream> #include<vector> using namespace std; const int MAX = 999; class Solution { public: void GetPath(vector<vector<int>>vec,int n) { vector<vector<int>>path(n); //初始化 for (int i = 0; i != n; i++) path[i].resize(n); for(int i=0;i!=n;i++) for (int j = 0; j != n; j++) { if (vec[i][j] != MAX)path[i][j] = j; else path[i][j] = -1; } for (int i = 0; i < n; i++)path[i][i] = -1; for(int k=0;k!=n;k++) for(int i=0;i!=n;i++) for (int j = 0; j != n; j++) { if (vec[i][k] + vec[k][j] < vec[i][j]) { vec[i][j] = vec[i][k] + vec[k][j]; path[i][j] = path[i][k]; } } for (int i = 0; i != n; i++) { cout << "\nStating from vertex: " << i << endl; bool flag = 0; for (int j = 0; j != n; j++) if (j != i && vec[i][j] < MAX) { flag = 1; cout << i << "->" << j << ":distance=" << vec[i][j] << ": " << i; int k = path[i][j]; while (k != j) { cout << "->" << k; k = path[k][j]; } cout << "->" << j << endl; } if (!flag)cout << "there's no path while starting from "<<i<<endl; } } }; int main() { ifstream putIn("D:\\Input.txt", ios::in); int num; int finalCount = 0; putIn >> num; const int x = num; vector<vector<int>>myVector(num); //myVector:带权邻接矩阵 for (int i = 0; i < num; i++) myVector[i].resize(num); for (int i = 0; i < num; i++) for (int j = 0; j < num; j++) { int temp; putIn >> temp; myVector[i][j] = temp; } Solution solution; cout << "Input文件中的邻接矩阵为\n"; for (auto x : myVector) { for (auto y : x)cout << y << '\t'; cout << endl; } solution.GetPath(myVector,num); return 0; }