弗洛伊德算法

foreveringxq

求弗洛伊德算法的具体介绍

紫辰

看数据结构的书
" S% |7 X% h! }2 D3 |/ Q/ `3 S: B

linmatsas

我记得我在数学实验的那本书里看过……

jians

怎么看不了？？？？？

foreveringxq

谢谢，这是我找到的一些资料，大家共享
# u# j5 z7 Z) e5 i算法基本思想
) {7 o' R" H9 B! |/ u) p7 H假设求顶点Vi到Vj的最短路径。弗洛伊德算法依次找从Vi到Vj，中间经过结点序号不大于0的最短路径，不大于1的最短路径，…直到中间顶点序号不大于n-1的最短路径，从中选取最小值，即为Vi到Vj的最短路径。

                算法具体描述
% n4 d" C( Y2 F5 z/ F若从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的最短路径长度。
' x4 R7 ]: l" Y) G* k1 v2 x% h- p9 O
* q5 Y) u( e" @              算法实现
void shortestpath_Floyd(Mgraph G,pathmatrix &[],Distancmatrix &D){
. U: M! M6 Y9 f3 A//用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

。。。。。。。。

dawan

好好搞啊，大家都努力

tianya-01

鉴定完毕！  

freeaward

试试运气啦~~~~~~~~~~~

wy371tt1

鉴定完毕！