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

每对顶点之间的最短路径

计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行n次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为O(n3)。第二种解决这一问题的方法是由Floyd R W提出的算法，称之为Floyd算法。

假设图G权的邻接矩阵为A0，

?a11?aA0??21????an1a12a22?an2?a1n??a2n?? ?????ann?来存放各边长度，其中：

aii?0

i?1,2,?,n；

aij??

i,j之间没有边，在程序中以各边都不可能达到

的充分大的数代替；

aij?wij

wij是i,j之间边的长度，i,j?1,2,?,n。

对于无向图，A0是对称矩阵，aij?aji。

Floyd算法的基本思想是：递推产生一个矩阵序列

A0,A1,?,Ak,?,An，其中Ak(i,j)表示从顶点vi到顶点vj的路径上所

经过的顶点序号不大于k的最短路径长度。

计算时用迭代公式：

Ak(i,j)?min(Ak?1(i,j),Ak?1(i,k)?Ak?1(k,j))

k是迭代次数，i,j,k?1,2,?,n。

最后，当k?n时，An即是各顶点之间的最短通路值。 例10某公司在六个城市c1,c2,?,c6中有分公司，从ci到cj的直接航程票价记在下述矩阵的(i,j)位置上。（?表示无直接航路），请帮助该公司设计一张城市c1到其它城市间的票价最便宜的路线图。

?0?50?????40?25??10402510?01520?25??1501020??? 201001025??2010055??25?25550?50?矩阵path用来存放每对顶点之间最短路径上所经过的顶点的序号。Floyd算法的Matlab程序如下： clear; clc; M=10000;

a(1,:)=[0,50,M,40,25,10]; a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6);

b=a+a';path=zeros(length(b)); for k=1:6 for i=1:6

for j=1:6

if b(i,j)>b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k; end end end end b, path

本文来源：https://www.bwwdw.com/article/3w8d.html