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); num; 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;
}
</vector<int></i<<endl;></vector<int></vector<int></vector></fstream></iostream>
Original: https://www.cnblogs.com/TomoyaAT/p/15526537.html
Author: TomoyaAT
Title: Floyd(动态规划)求解任意两点间的最短路径(图解)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584129/
转载文章受原作者版权保护。转载请注明原作者出处！