Floyd算法每对顶点之间的最短路径.doc

《Floyd算法每对顶点之间的最短路径.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理勿做商业用途每对顶点之间的最短路径计算赋权图中各对顶点之间最短路径,显然可以调用Dijｋsｔra算法。具体方法是:每次以不同的顶点作为起点，用Dijksｔra算法求出从该起点到其余顶点的最短路径，反复执行次这样的操作,就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为。第二种解决这一问题的方法是由FlｏｙdRW提出的算法,称之为Fｌｏyd算法。假设图权的邻接矩阵为,来存放各边长度，其中:　；　之间没有边,在程序中以各边都不可能达到的充分大的数代替；　是之间边的长度,。对于无向图，是对称矩阵，。Flｏ

2、yd算法的基本思想是：递推产生一个矩阵序列,其中表示从顶点到顶点的路径上所经过的顶点序号不大于的最短路径长度。计算时用迭代公式：是迭代次数，。个人收集整理勿做商业用途最后,当时，即是各顶点之间的最短通路值。例10某公司在六个城市中有分公司，从到的直接航程票价记在下述矩阵的位置上。（表示无直接航路),请帮助该公司设计一张城市到其它城市间的票价最便宜的路线图。矩阵paｔh用来存放每对顶点之间最短路径上所经过的顶点的序号。Floyd算法的Matlａb程序如下：cleａr;clc;M=１0000;a(１,：)=[0,50,Ｍ,４0,

3、2５，１0];a(2,:)＝[ｚｅｒos（1，２),１5,２0,M,25];a(3，：)＝[zeroｓ（１，3),１0,２０,Ｍ];a(4,：)=[zeros(1,4）,１0,25];a（５,:)=[zeroｓ(1，5),５5];ａ(6,：)=zeros(1,6);b＝ａ＋a';path=zeroｓ(lengｔｈ(b));ｆork=1：6　fori=１:６个人收集整理勿做商业用途ｆｏr　j=１:6　　　　ｉfb(i，j)>b(i,ｋ)+ｂ(ｋ,j)　　b(ｉ,j)＝b（i,ｋ)+b（k,j);　pａth(i,j)=k；　　　

4、　end　endｅndｅndb,　ｐath