Floyd算法每对顶点之间的最短路径
- 格式：doc
- 大小：74.50 KB
- 文档页数：3
百度文库 - 让每个人平等地提升自我
1
每对顶点之间的最短路径
计算赋权图中各对顶点之间最短路径，显然可以调用
Dijkstra算法。具体方法是：每次以不同的顶点作为起点，
用Dijkstra算法求出从该起点到其余顶点的最短路径，反复
执行n次这样的操作，就可得到从每一个顶点到其它顶点的
最短路径。这种算法的时间复杂度为)(3nO。第二种解决这一
问题的方法是由Floyd R W提出的算法，称之为Floyd算法。
假设图G权的邻接矩阵为0A，
nnnnnnaaaaaaaaaA
21
22221
11211
0
来存放各边长度，其中：
0iia
ni,,2,1
；
ija
ji,
之间没有边，在程序中以各边都不可能达到的
充分大的数代替；
ijijwa ij
w
是ji,之间边的长度，nji,,2,1,。
对于无向图，0A是对称矩阵，jiijaa。
Floyd算法的基本思想是：递推产生一个矩阵序列
nkAAAA,,,,,10，其中),(jiAk表示从顶点i
v
到顶点jv的路径上所
经过的顶点序号不大于k的最短路径长度。
计算时用迭代公式：
)),(),(),,(min(),(111jkAkiAjiAjiAkkkk
k
是迭代次数，nkji,,2,1,,。
百度文库 - 让每个人平等地提升自我
2
最后，当nk时，nA即是各顶点之间的最短通路值。
例10某公司在六个城市621,,,ccc中有分公司，从ic到jc的
直接航程票价记在下述矩阵的),(ji位置上。（表示无直接航
路），请帮助该公司设计一张城市1c到其它城市间的票价最便
宜的路线图。
055252510
550102025
25100102040
2010015
252015050
102540500
矩阵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
百度文库 - 让每个人平等地提升自我
3
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
