之前我们接触学习了Dijkstra算法求解一个顶点到其他各个顶点的最短路径和距离,但如果我们想知道每一对顶点的最短路径和距离时,可以通过以每一个顶点作为源点循环求出每对顶点之间的最小距离。除此之外,我们可以利用本篇博客即将学习的弗洛伊德(Floyd)算法来求两顶点之间的最短距离。
弗洛伊德(Floyd)算法
1)算法思想原理:
从任意节点i到任意节点j的最短路径不外乎2种可能,1是直接从i到j,2是从i经过若干个节点k到j。所以,我们假设Dis(i,j)为节点u到节点v的最短路径的距离,对于每一个节点k,我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,证明从i到k再到j的路径比i直接到j的路径短,我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j),这样一来,当我们遍历完所有节点k,Dis(i,j)中记录的便是i到j的最短路径的距离。
2).算法描述:
a.从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。
b.对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
3)具体实现步骤
要操作的有向图如图所示:
用邻接矩阵表示为:
#define INF 99999 //表示不可到达 #define MAXSIZE 4 //表示图的结点数 //邻接矩阵存储图的信息 int map[MAXSIZE][MAXSIZE]={ {0,5,INF,7}, {INF,0,4,2}, {3,3,0,2}, {INF,INF,1,0} };
定义
A[MAXSIZE][MAXSIZE]: A[i][j]表示当前顶点i到j的最短距离
path[MAXSIZE][MAXSIZE]: 保存最短路径
Floyd算法过程矩阵的计算----十字交叉法
先初始化2个数组:
//数据初始化 for(int i=0;i<MAXSIZE;i++) { for(int j=0;j<MAXSIZE;j++) { A[i][j]=map[i][j]; path[i][j]=-1;//初始化为-1 } }
即得到:
1)使用十字交叉法,划去第0行和第0列以及左对角线,即
此时不在这三条线上的数据有:A[1][2]=4;A[1][3]=2;A[2][3]=2;A[2][1]=3等6个数。
此时根据Ak(i,j) = min( Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j) )对比看是否要数据更新
例如看A[2][1]=3这个数是否要更新。
此时A[0][1]+A[2][0]=8>A[2][1]=3
所以不用更新,其他5和数都是这样判断,会发现都不用更新
1)使用十字交叉法,划去第1行和第1列以及左对角线,即
此时不在这3条线上的数据依次是:A[0][2],A[0][3],A[2][0],A[2][3],A[3][0],A[3][2]
我们来看数据A[0][2]。
发现
A[0][2]>A[0][1]+A[1][2]=5+4=9(图中画出矩形顶点的和,即A[0][2]附近2个顶点的和,不是对角线那个顶点);
此时修改A[0][2]=9,path[0][2]=1(即划去的行号和列号,也是3条线交点的坐标)
按照此方法检查其他剩下的5个数,最后得到
以此类推。最后得到:
理解清楚步骤后,写出Floyd算法代码为:
//弗洛伊德算法 void Floyd() { int path[MAXSIZE][MAXSIZE];//保存最短路径 int A[MAXSIZE][MAXSIZE];//a[i][j]表示当前顶点i到j的最短距离 //数据初始化 for(int i=0;i<MAXSIZE;i++) { for(int j=0;j<MAXSIZE;j++) { A[i][j]=map[i][j]; path[i][j]=-1;//初始化为-1 } } for(int diagonal=0;diagonal<MAXSIZE;diagonal++)//左对角线 { for(int k=0;k<MAXSIZE;k++)//行 { if(k!=diagonal)//除去此行所有的点 for(int j=0;j<MAXSIZE;j++)//列 { if(j!=diagonal)//除去此列所以的点 { if(k!=j)//除去对角线的点 { if(A[k][j]>A[diagonal][j]+A[k][diagonal])//满足条件 { A[k][j]=A[diagonal][j]+A[k][diagonal]; path[k][j]=diagonal; } } } } } } }
得到A[MAXSIZE][MAXSIZE]和path[]数组后。
A[i][j]: 表示从顶点i到顶点j的最短距离。
而最短路径还要通过path[]数组计算得来。计算方法如下:
例如我们求解顶点3到顶点1的最小距离和路径:
最小距离:A[3][1]=4
最短路径:
path[3][1]=2;
path[2][1]=-1(一旦值为-1,停止计算)
所以顶点1前面经过的是顶点2,
即最后路径为:
3->2->1;
j结果显示代码为:
//结果输出: for(int i=0;i<MAXSIZE;i++) { for(int j=0;j<MAXSIZE;j++) { if(A[i][j]==INF) cout<<"从顶点"<<i<<"到顶点"<<j<<"不存在路径"<<endl; else { cout<<"从顶点"<<i<<"到顶点"<<j<<"最短距离为: "<<A[i][j]<<" 其路径为:"; vector<int>temp; temp.insert(temp.begin(),j);//把终点插入 int ok1=i,ok2=j; while(true) { ok1=path[ok1][ok2]; if(ok1==-1) break; temp.insert(temp.begin(),ok1); } temp.insert(temp.begin(),i);//把起点插入 for(int z=0;z<temp.size();z++) cout<<temp[z]<<" "; cout<<endl; } } }
最终程序结果:
附上源码地址:https://github.com/longpo/algorithm/tree/master/Floyd
相关推荐
算法-最短路径-Floyd算法
最短路径算法 floyd
最短路径(Floyd-Warshall)
最短路径 Short path Floyd Floyd求最短路径
C# floyd算法 求最短路径 C# floyd算法 求最短路径 C# floyd算法 求最短路径
该程序是我写的博客“一起talk C栗子吧(第五十五回:C语言实例--图的最短路径三)”的配套程序,共享给大家使用
对同一场景分别进行dijkstra算法求指定节点间的最短路径,floyd求任意端间最短路径。 报告中含C++代码
Floyd最短路径算法的java实现,文件内附测试用例拓扑。
本节内容王道考研/CSKAOYAN.COM最短路径Floyd算法王道考研/CSKAOYAN.COM罗伯特·弗洛伊德1978年图灵奖得主• Floyd算法(Flo
求最短路径的Floyd算法实现,无向图和有向图均适用。1先区别有向图和无向图,2输入顶点数和边数并检查合法性,3输入每边的起点、终点、权重并检查合法性,并初始化邻接矩阵和路径矩阵,4调用自定义函数Floyd
Floyd算法直接使用二维数组求出所有顶点到所有顶点的最短路径。 D代表顶点到顶点的最短路径权值和的矩阵。 P代表对应顶点的最小路径的前驱矩阵。 以下程序在DEV C++中调试运行通过。 #include <stdio> #define ...
最短路径floyd算法实现最短路径floyd算法实现最短路径floyd算法实现最短路径floyd算法实现
基于C++实现的每对结点之间的最短路径(Floyd-Warshall算法)
Floyd-Warshall算法,又叫Floyd算法,用于求每对顶点之间最短路径
最短路径floyd算法最短路径floyd算法最短路径floyd算法最短路径floyd算法
floyd算法是求解最短路径的一种经典算法,本文分析了它求解最短路径的具体实现方法和效率,希望对大家对floyd算法有所了解。
08最短路径_Floyd.c
一种用于寻找给定的加权图中顶点间最短路径的matlab算法,通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
最短路径_Floyd算法_matlab实现.doc