基于数学软件的Floyd算法的实现

《基于数学软件的Floyd算法的实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于数学软件的Floyd算法的实现徐昌贵卢鹏（西南交通大学峨眉校区，四川峨眉614202）摘要：Floyd算法是图论中求一个图中任意两顶点间最短距离的一种算法。本文给出了实现Floyd算法的步骤，并给11!了用数学软件Matlab与Mathematica实现Floyd算法的程序，可供同行们参考。关键词：Floyd算法，数学软件，Matlab»MathematicaFloyd算法是图论中求一个图中任意两顶点间最短距离的一种算法。Matlab与Mathematica是著名的3M数学软件中的其中两个，在工程计算，科学研究，数学建模比赛中有广泛的应用。本人在长期的数学建模培训中，根据Floyd算法的

2、原理编写了用Matlab与Mathematica这两个数学软件实现该算法的程序。1Floyd算法Floyd算法能实现求一个图中任意两顶点间的最短距离，并给出最短路径，并且对有向图和无向图都适合。Floyd算法的基本思想⑴是通过递推产生一个矩阵序列人）/],…,^,…，观,其中Ak（i,j）表示从顶点V,-到顶点Vj的路径上所经过的顶点序号不大于P的最短路径长度。计算时用迭代公式：AGj）=min（4_iQ,jA_i0；k）+A-i伙,»）这里k是迭代次数,=…,n。最后，当k=n时，人即是各顶点之间的最短距离。设图G的顶点数为n,D=（dij）“n为其距离矩阵，实现Floyd算法的步骤如下

3、:【Step1]输入距离矩阵D；[Step2]定义初值k=l；【Step3]赋值i=l；LStep4]dij=min（dij,dik+dkj）,j=l,2,...,n;[Step5]i-H-；如菓i

4、需要可以进行修改*）M=99999;(*足够大的一个数，是系统的一个上界*)T={{0,20,14,M,M,M,M},{M,0,M,15,12,M,M},10,M,13,M},{M,MM0,8,M,9},{M,M,M,M,0,8,10},{M,M,M,M,M,0,12},{M,M,M,M,M,M,O}};(*图的距离矩阵，可以是有向图或无向图*)B=Tablc[{i,j},{i,n},{j,n}];For[k=1,kv=n,k++,For[i=1,i<=n,汁+,If[k!=i,For[j=l,jv=n,j++,If[i!=j&&k!=j&&T[[i,j]]>T[[i,k]]+T[[k,j]

5、],T[[iJ]]=T[[i,k]]+T[[k,j]];p=Delete[B[[k,j]],1];B[[i,j]]=Join[B[[i,kJ],p];]]]]]；Print[n任意两城市之间的最短路：”,MatrixForm[T]];(*T为最短路*)Print[n任意两城市之间的最短路的路径:”,MatrixForm[B]]；(*B为最短路径*)1Floyd算法的Matlab实现下面是求最短路问题的Floyd算法的Matlab实现程序。采用Matlab7.0版本,在WINXP操作系统环境下调试运行通过。先建立一个floyd.m的文件：function[d,r]=floyd(a)n=size

6、(a,l);d=a;fori=l:nforj=l:nendendr；fork=l:nfori=l:nforj=l:nifd(i,k)+d(k,j)

7、2014MMMM0M1512MMMM010M13MMMM08M9MMMM0810MMMMM012MMMMM用上面编写的mathematica程序运行的结果如下:020142432273399999099999151220229999999999010181319999999999999999081699999999999999999999908109999999999999999999999999012599