数学建模社区-数学中国

标题: 弗洛伊德算法 [打印本页]

作者: foreveringxq 时间: 2010-8-7 20:57
标题: 弗洛伊德算法
求弗洛伊德算法的具体介绍

作者: 紫辰 时间: 2010-8-7 21:34
看数据结构的书

作者: linmatsas 时间: 2010-8-7 23:40
我记得我在数学实验的那本书里看过……

作者: jians 时间: 2010-8-8 09:38
怎么看不了？？？？？

作者: foreveringxq 时间: 2010-8-8 10:29
谢谢，这是我找到的一些资料，大家共享
算法基本思想
假设求顶点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(Mgraph G,pathmatrix &

[],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

[v][w][w]=true; }//if}//forfor (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 　给出一个图，求最短路径问题的一个O(n^3)算法优点：容易理解，可以算出任意两个节点之间最短距离的算法，程序容易写缺点：复杂度达到三次方，不适合计算大量数据
Floyd算法的功能是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵.它的功能看上去挺强大的,但它的实现却很简单,和Washall算法很相似,也是一个三层循环,思路也是相似是,就是利用前面计算的结果:核心思想：设立[i,j]为权值在这里有个地方要注意一下，就是最外层的循环k是一个中间的跳板，必须放在中间，不然就找不到最小的值for(k=0;k<len;k++)for(i=0;i<len;i++)for(j=0;j<len;j++)if(a[i,k]+a[k,j]<a[i,j])a[i,j]=a[k,j]+a[i,k];

作者: wajm_011 时间: 2010-8-8 10:57
。。。。。。。。

作者: dawan 时间: 2010-8-8 11:20
好好搞啊，大家都努力

作者: tianya-01 时间: 2010-8-26 11:33
鉴定完毕！

作者: freeaward 时间: 2010-8-26 11:34
试试运气啦~~~~~~~~~~~

作者: wy371tt1 时间: 2010-8-26 11:35
鉴定完毕！

作者: fengzhisheng106 时间: 2010-8-26 11:36
强人，佩服死了。呵呵，不错啊

作者: 想做就做 时间: 2010-8-26 11:38
强人，佩服死了。呵呵，不错啊

作者: nbvcxz 时间: 2010-8-26 11:46
我基本上是采用看英语文章的办法，先泛读，再精读，再一句一句看，最后再提纲挈领，总算是明白一点了，当然，也可能还是领悟错了。最后要说的一句话是：楼主，你很牛叉，希望你不是真的有病。

作者: erwinbsb 时间: 2010-8-26 13:52
强人，佩服死了。呵呵，不错啊

作者: surfw 时间: 2010-8-26 18:59
试试运气啦~~~~~~~~~~~

作者: xiaoai 时间: 2010-8-26 19:17
强人，佩服死了。呵呵，不错啊

作者: 阿里wudi 时间: 2010-8-27 00:00
楼主，你写得实在是太好了。我惟一能做的，就只有把这个帖子顶上去这件事了

作者: liushuei_0 时间: 2010-8-27 08:00
试试运气啦~~~~~~~~~~~

作者: 帮忙 时间: 2010-8-27 12:00
哦～～

作者: ycy74_2005 时间: 2010-8-27 15:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~

作者: guohuawin 时间: 2010-8-27 20:00
声明一下：本人看贴和回贴的规则，好贴必看，精华贴必回。

作者: 一切遂愿 时间: 2010-8-28 08:00
(*^__^*) 指点系词……激扬文字……

作者: zhutianzheng 时间: 2010-8-28 12:00
不错不错,我喜欢看

作者: ggg 时间: 2010-8-28 15:00
声明一下：本人看贴和回贴的规则，好贴必看，精华贴必回。

作者: as1 时间: 2010-8-28 20:00
强人，佩服死了。呵呵，不错啊

作者: wentian53 时间: 2010-8-28 23:59
我基本上是采用看英语文章的办法，先泛读，再精读，再一句一句看，最后再提纲挈领，总算是明白一点了，当然，也可能还是领悟错了。最后要说的一句话是：楼主，你很牛叉，希望你不是真的有病。

作者: winifreder 时间: 2010-8-29 08:00
试试运气啦~~~~~~~~~~~

作者: stoneman 时间: 2010-8-29 12:00
鉴定完毕！

作者: uestczgm 时间: 2010-8-29 15:00
哦～～

作者: Idesire 时间: 2010-8-29 20:00
声明一下：本人看贴和回贴的规则，好贴必看，精华贴必回。

作者: JoeyGo 时间: 2010-8-30 12:00
(*^__^*) 指点系词……激扬文字……

作者: zzdyp 时间: 2010-8-30 15:00
哦～～

作者: avriling 时间: 2010-8-30 20:00
楼主，你写得实在是太好了。我惟一能做的，就只有把这个帖子顶上去这件事了

作者: yh0148 时间: 2010-8-31 08:00
试试运气啦~~~~~~~~~~~

作者: yingcaiwf 时间: 2010-8-31 12:00
不错不错,我喜欢看

作者: haohaizi66 时间: 2010-8-31 15:00
留个脚印```````

作者: bigboy 时间: 2010-8-31 20:01
强人，佩服死了。呵呵，不错啊

作者: dadikangxi 时间: 2010-9-1 08:00
顶顶更健康，越顶吃的越香。

作者: XIAOBO8814 时间: 2010-9-1 12:00
试试运气啦~~~~~~~~~~~

作者: uhvsufo 时间: 2010-9-1 12:00
看起来好~~像啊~~~~~

作者: jianchuy 时间: 2010-9-1 15:00
强人，佩服死了。呵呵，不错啊

作者: 007feidao 时间: 2010-9-1 20:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~

作者: pgfzhy 时间: 2010-9-2 12:00
强人，佩服死了。呵呵，不错啊

作者: irico 时间: 2010-9-2 15:00
楼主，你写得实在是太好了。我惟一能做的，就只有把这个帖子顶上去这件事了

作者: iambamboo 时间: 2010-9-2 20:00
留个脚印```````

作者: as 时间: 2010-9-3 12:00
我要把这个帖子一直往上顶，往上顶！

作者: ygyu 时间: 2010-9-3 15:00
顶顶更健康，越顶吃的越香。

作者: rachel7364 时间: 2010-9-3 20:00
我基本上是采用看英语文章的办法，先泛读，再精读，再一句一句看，最后再提纲挈领，总算是明白一点了，当然，也可能还是领悟错了。最后要说的一句话是：楼主，你很牛叉，希望你不是真的有病。

作者: hitjzm 时间: 2010-9-4 08:00
留个脚印```````

作者: wowttycccc 时间: 2010-9-4 12:00
顶顶更健康，越顶吃的越香。

作者: junlisa 时间: 2010-9-4 15:00
哦～～

作者: squirrellin 时间: 2010-9-4 20:00
我要把这个帖子一直往上顶，往上顶！

作者: lu0000hb61 时间: 2010-9-5 12:00
不错不错,我喜欢看

作者: jiangsy 时间: 2010-9-5 15:00
强人，佩服死了。呵呵，不错啊

作者: wulingren 时间: 2010-9-5 20:00
楼主的帖子实在是写得太好了。可是我立刻想到，这么好的帖子，倘若别人看不到，那么不是浪费楼主的心血吗？经过痛苦的思想斗争，我终于下定决心，牺牲小我，奉献大我。我要拿出这帖子奉献给世人赏阅，我要把这个帖子一直往上顶，往上顶！顶到所有人都看到为止！

作者: haipop 时间: 2010-9-6 12:00
留个脚印```````

作者: 940fen 时间: 2010-9-6 15:00
哦～～

作者: loverose 时间: 2010-9-6 20:00
强人，佩服死了。呵呵，不错啊

作者: alair002 时间: 2012-1-13 20:25
没有体力啦，资料能发给我一份吗？我的邮箱是18633525948圈163邮箱，谢啦

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)