Floyd All Shortest Path 所有最短路径的查找在严慧敏这本书也有介绍,但是这本书是讲数据结构的,没有介绍这个算法是什么算法,其实这个算法是动态规划法。
思路:
1 用一个矩阵来记录从i到j的最短路径
2 用三层循环,选好一个点k,然后把所有其他点组成两对i和j;测试从i到j是直接走近,还是从i经过k最后到j比较近一点。如果绕道k之后花费更小一点,那么就更新[i][j]的数据。
3 循环完毕就记录了所有两点之间的最短距离了。
看下面的实现程序,用了两个循环,第一循环是赋值给记录最短路径的矩阵,第二个循环就是实际记录最短路径的算法。
用了两个矩阵,第二个矩阵是为了可以打印出来两点之间的最短路径都经过了那些点:
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
vector<vector<vector<int> > > FloydAllShortestPath(vector<vector<int> >& matrixGraph,
vector<vector<vector<int> > >& pathM)
{
int n = matrixGraph.size();
vector<vector<vector<int> > > allPathNum(n);
pathM.resize(n);
for (int i = 0; i < n; i++)
{
allPathNum[i].resize(n);
pathM[i].resize(n);
for (int j = 0; j < n; j++)
{
allPathNum[i][j].resize(n+1);
allPathNum[i][j][0] = matrixGraph[i][j];
pathM[i][j].resize(n+1);
}
}
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
allPathNum[i][j][k+1] = min(allPathNum[i][j][k],
allPathNum[i][k][k] + allPathNum[k][j][k]);
pathM[i][j][k] = allPathNum[i][j][k]>allPathNum[i][k][k]+
allPathNum[k][j][k]? 1:0;
}
}
}
return allPathNum;
}
};
测试主程序太大了,所以分开比较好看:
int main()
{
int a[] = {0, 2, 9};
vector<int> v(a, a+3);
vector<vector<int> > vArray;
vArray.push_back(v);
v[0] = 8 ;v[1] = 0; v[2] = 6;
vArray.push_back(v);
v[0] = 1 ;v[1] = INT_MAX; v[2] = 0;
vArray.push_back(v);
for(auto x: vArray)
{
for(auto y:x)
cout<<y<<"\t";
cout<<endl;
}
cout<<endl;
vector<vector<vector<int> > > allPathNum;
vector<vector<vector<int> > > pass;
Solution solu;
allPathNum = solu.FloydAllShortestPath(vArray, pass);
for(auto x: allPathNum)
{
for(auto y:x)
{
for(auto z:y)
cout<<z<<"\t";
cout<<endl;
}
cout<<endl;
}
cout<<endl;
for(int i=0; i< pass.size(); i++)
{
for (int j = 0; j < pass[i].size(); j++)
{
cout<<"Vector "<<i<<" to "<<j<<" pass:";
for (int k = 0; k < pass[i][j].size(); k++)
{
if(pass[i][j][k] == 1)
cout<<k<<"\t";
}
cout<<endl;
}
cout<<endl;
}
system("pause");
return 0;
}
这里是打印了三个矩阵,第一是记录路径的矩阵;
第二个是记录最短路径的矩阵,这是中间那个三维矩阵,第一矩阵表示第一个点到其他三点的最短路径,如第一行是原始的直接从第一点到其他点的距离,中间不经过任何其他点,第二行是指测试了加入第一个点作为中间路径,第三行是指测试了加入第二个点作为中间路径,第四行是指测试了加入第三点作为中间路径;可以看出第一点到第三点的最短路径是经过了第二个点。
其路径如下图:
第三个是计算经过路径的矩阵,如果看第二个三维矩阵不好看,那么这里打印就是为了方便观察的。这里的下标是从0开始。
运行结果:
分享到:
相关推荐
C# floyd算法 求最短路径 C# floyd算法 求最短路径 C# floyd算法 求最短路径
floyd计算最短路径,只需要更改邻接矩阵
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。采用C++实现
Floyd最短路径算法的java实现,文件内附测试用例拓扑。
Floyd算法的C++ 实现,终端输入终端输出
本程序中的20个城市点的坐标是自己随便设的,两城市之间的费用是随机生成的,要么相通,想通则是大于两城市之间的欧几里得距离的,开发平台为VS2008 实现语言为C++
基于Floyd算法实现北京地铁最短路径规划Python仿真源码(课程设计).zip 已获导师指导并通过的97分的高分课程设计项目,可作为课程设计和期末大作业,下载即用无需修改,项目完整确保可以运行。 基于Floyd算法实现...
最短路径算法 floyd
Floyd算法是经典的最短路径算法之一,应用广泛,可以求解多对多和一对一的最短路;
求最短路径的Floyd算法实现,无向图和有向图均适用。1先区别有向图和无向图,2输入顶点数和边数并检查合法性,3输入每边的起点、终点、权重并检查合法性,并初始化邻接矩阵和路径矩阵,4调用自定义函数Floyd
用MFC来完成Floyd算法的最短路径基本功能求法(有界面)。
floyd算法是求解最短路径的一种经典算法,本文分析了它求解最短路径的具体实现方法和效率,希望对大家对floyd算法有所了解。
对同一场景分别进行dijkstra算法求指定节点间的最短路径,floyd求任意端间最短路径。 报告中含C++代码
构造邻接矩阵,利用Floyd算法求最短路径。课程设计~~~
floyd算法,求最短路径的权值,java实现的
该课件采用C++面向对象思想,对最短路径中的弗洛伊德算法进行完美演示,开发工具VC6.0,对于初学数据结构的学生比较合适。
最短路径(Floyd-Warshall)
使用两种最常用的方法求解最短路径问题,关注于算法的实现!
Floyd-最短路径 C#程序 确定边权重计算任意顶点间的最短路径
最短路径 Short path Floyd Floyd求最短路径