弗洛伊德算法详解 弗洛伊德算法流程图

算法的数据结构弗洛伊德算法采用图的带权邻接矩阵存储结构。
算法基本思想
假设求顶点Vi到Vj的最短路径。弗洛伊德算法依次找从Vi到Vj,中间经过结点序号不大于0的最短路径,不大于1的最短路径,…直到中间顶点序号不大于n-1的最短路径,从中选取最小值,即为Vi到Vj的最短路径。
算法具体描述
若从Vi到Vj有弧,则从Vi到Vj存在一条长度为弧上权值(arcs[i][j])的路径,该路径不一定是最短路径,尚需进行n次试探。
首先考虑从Vi到Vj经过中间顶点V0的路径(Vi,V0,Vj)是否存在,也就是判断弧(Vi,V0)和(V0,Vj)是否存在。若存在,则比较(Vi,Vj)和(Vi,V0,Vj)的路径长度取较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。
在此路径上再增加一个顶点V1,也就是说,如果(Vi,…V1)和(V1,…Vj)分别是当前找到的中间顶点序号不大于0的最短路径,那么,(Vi,…V1,…Vj)就有可能是从Vi到Vj的中间顶点序号不大于1的最短路径。将它和已经得到的从Vi到Vj中间顶点序号不大于0的最短路径相比较,从中选出最短的作为从Vi到Vj中间顶点序号不大于1的最短路径。
然后,再增加一个顶点V2继续进行这个试探过程。
一般情况下,若(Vi,…Vk)和(Vk,…Vj)分别是从Vi到Vk和从Vk到Vj的中间顶点序号不大于k-1的最短路径,则将(Vi,…,Vk,…Vj)和已经得到的从Vi到Vj的中间顶点序号不大于k-1的最短路径相比较,其长度最短者即为从Vi到Vj的中间顶点序号不大于k的最短路径。
经过n次比较之后,最后求得的便是从Vi到Vj的最短路径。
按此方法可同时求得各对顶点之间的最短路径。
现定义一个n阶方阵序列
D(-1),D(0),D(1),…,D(k),…,D(n-1)
其中
D(-1)[i][j]=arcs[i][j]
D(k)[i][j]=Min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}0≤k≤n-1
上述公式中,D(1)[i][j]是从Vi到Vj的中间顶点序号不大于k的最短路径长度;D(n-1)[i][j]是从Vi到Vj的最短路径长度。
算法实现
void shortestpath_Floyd(MgraphG,pathmatrix &P[],Distancmatrix &D){//用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其带权路径长度D[v][w]。
弗洛伊德算法详解 弗洛伊德算法流程图
//若P[v][w][u]为TRUE,则u是从v到w当前求得最短路径上的顶点。
For(v=0;v<G.vexnum;++v)//各对顶点之间路径和距离初始化
For(w=0;w<G.vexnum;++w){
D[v][w]=G.arcs[v][w];
For(u=0;u<G.vexnum;++u)P[v][w][u]=false;
If(D[v][w]<INFINITY){//从v到w有直接路径
P[v][w][v]=true;P[v][w][w]=true;
}//if
}//for
for (u=0;u<G.vexnum;++u)
for (v=0;v<G.vexnum;++v)
for (w=0;w<G.vexnum;++w)
if(D[v][u]+D[u][w]<D[v][w]){//从v经u到w的一条路径更短
D[v][w]= D[v][u]+D[u][w];
For (I=0;I<G.vexnum;++I)
P[v][w][I]=P[v][u][I]|| P[u][w][I];
}//if
}//shortestpath_Floyd
 

  

爱华网本文地址 » http://www.413yy.cn/a/25101017/367223.html

更多阅读

如何填写政治面貌?详解 如何查看自己政治面貌

如何填写政治面貌?【详解】——简介政治面貌可不是指的人的外貌,政治面貌其实是一个人的政治身份。对于我们普通公民而言,政治身份似乎没有什么影响,但是对于当权者或者机构组织而言,政治面貌就很重要了,在对个人考察方面或者职位提升方面

不同脸型适合画眉方法,详解眉毛的画法 方脸型画眉

?特写看一下...  对于圆脸型的妹子来说,需要有一些角度的眉毛,把眉峰吊起来,让脸型看起来更有棱角一些~对于下巴比较宽或者太阳穴比较窄的妹纸,美貌的形状要大气自然,而且要适当的短一些,并且加重眉头部分不同脸型适合画眉方法,详解

100道门2013攻略100关图文详解:1 第1~10关

100道门2013攻略100关图文详解:[1]第1~10关——简介100道门2013是安卓平台一款新颖的解密益智游戏,你需要在房间中发现线索,然后把门打开进入下一个房间。每一个房间的主题都不一样,将给你带来百次不同的游戏体验!100道门2013攻略100关

CSOL咆哮怒焰M14EBR详解以及专业强化分析 csol咆哮怒焰强化

众所周知,咆哮怒焰系列是威力最大的突击步枪,其高威力以及不俗的精准度让它成为了一把点射神器。而强化系统更是让这把大威力步枪如虎添翼,咆哮怒焰可以算是最值得强化的几把枪支之一了。下面是这把枪的简略评测,以及它的强化详解。大家

研究生网上报名流程 超详解 2017研究生报名流程

研究生网上报名流程 【超详解】——简介现在开始报名的话,是针对应届的毕业生的,不过过段时间都可以报名的。流程都是一样的。研究生网上报名流程 【超详解】——方法/步骤研究生网上报名流程 【超详解】 1、首先,我们搜索,进入到中国

声明:《弗洛伊德算法详解 弗洛伊德算法流程图》为网友一点都不酷分享!如侵犯到您的合法权益请联系我们删除