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

基于数学软件的Floyd算法的实现徐昌贵 卢鹏（西南交通大学峨眉校区，四川峨眉 614202）摘要：Floyd算法是图论中求一个图中任意两顶点间最短距离的一种算法。本文给出了实现Floyd算法的步骤，并给出了用数学软件Matlab与Mathematica实现Floyd算法的程序，可供同行们参考。关键词：Floyd算法，数学软件，Matlab，MathematicaFloyd算法是图论中求一个图中任意两顶点间最短距离的一种算法。Matlab与Mathematica是著名的3M数学软件中的其中两个，在工程计算，科学研究，数学建模比赛中有广泛的应用。本人在长期的数学建模培训中，根据Floyd算法的原理编写了用Matlab与Mathematica这两个数学软件实现该算法的程序。1 Floyd算法Floyd算法能实现求一个图中任意两顶点间的最短距离，并给出最短路径，并且对有向图和无向图都适合。Floyd算法的基本思想1是通过递推产生一个矩阵序列，其中表示从顶点到顶点的路径上所经过的顶点序号不大于的最短路径长度。计算时用迭代公式：这里是迭代次数，。最后，当时，即是各顶点之间的最短距离。设图G的顶点数为n，D=(dij)nn为其距离矩阵，实现Floyd算法的步骤如下：【Step 1】输入距离矩阵D；【Step 2】定义初值k=1；【Step 3】赋值i=1；【Step 4】dij=min(dij,dik+dkj)，j=1,2,n;【Step 5】i+；如果in，转Step 4；【Step 6】k+；如果kn，转Step 3；否则转Step 7；【Step 7】程序结束，输出结果。2 Floyd算法的Mathematica实现 下面是求最短路问题的Floyd算法的Mathematica实现程序，其中语句后面“（*”和“*）”之间的为注释，不影响程序的运行。采用Mathematica5.0版本，在WINXP操作系统环境下调试运行通过。n = 7; (*图的顶点数，根据需要可以进行修改*) M = 99999; (*足够大的一个数，是系统的一个上界*) T =0,20,14,M,M,M,M, M,0,M,15,12,M,M, M,M,0,10,M,13,M, M,M,M,0,8,M,9, M,M,M,M,0,8,10, M,M,M,M,M,0,12, M,M,M,M,M,M,0; (*图的距离矩阵, 可以是有向图或无向图*)B = Tablei, j, i, n, j, n; Fork = 1, k = n, k+, Fori = 1, i = n, i+, Ifk != i, Forj = 1, j Ti, k + Tk, j, Ti, j = Ti, k + Tk, j; p = DeleteBk, j, 1; Bi, j = JoinBi, k, p; ;Print任意两城市之间的最短路：, MatrixFormT; (*T为最短路*)Print任意两城市之间的最短路的路径:,MatrixFormB；(* B为最短路径*)3 Floyd算法的Matlab实现下面是求最短路问题的Floyd算法的Matlab实现程序。采用Matlab7.0版本，在WINXP操作系统环境下调试运行通过。先建立一个floyd.m的文件：function d,r=floyd(a) n=size(a,1); d=a; for i=1:n for j=1:n r(i,j)=j; end end r; for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j)d(i,j) d(i,j)=d(i,k)+d(k,j); r(i,j)=r(i,k); end end end k; d; r; end r然后在命令窗口中输入：M=99999; a=0,20,14,M,M,M,M M,0,M,15,12,M,M M,M,0,10,M,13,M M,M,M,0,8,M,9 M,M,M,M,0,8,10 M,M,M,M,M,0,12 M,M,M,M,M,M,0;length=floyd(a)4 算例如下图是一个7个顶点的有向图，现需计算任意两顶点间的最短距离及最短路径。该图的距离矩阵为（M表示一个充分大的正数）：用上面编写的mathematica程序运行的结果如下：从结果可以清楚的看到，从顶点到顶点的最短路为33，最短路径为。用上面编写的Matlab程序运行的结果如下： 可见，两个软件运行的结果是一致的。参考文献1 卢开澄，卢华明：图论及其应用（第2版），北京：清华大学出版社，2003年11月，第90-94页作者简介：徐昌贵（1970-），男，四川广汉人，四川峨眉西南交通大学