最短路径的Floyd算法的Matlab程序
每对顶点之间的最短路径
计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是:每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行n次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为
3。第二种解决这一问题的方法是由Floyd R W提出的算法，称之为Floyd算法。 O(n)
G假设图权的邻接矩阵为， A0
aaaL，，11121n,,aaaL21222n,,A, 0,,MMLM
,,aaaLnnnn12，，
来存放各边长度，其中:
; a,0in,1,2,,Lii
之间没有边，在程序中以各边都不可能达到的充分大的数代替; a,,i,jij
是之间边的长度，。 a,wwi,jijn,1,2,,,Lijijij
对于无向图，是对称矩阵，a,a。 Aijji0
Floyd算法的基本
思想
教师资格思想品德鉴定表下载浅论红楼梦的主题思想员工思想动态调查问卷论语教育思想学生思想教育讲话稿
是:递推产生一个矩阵序列，其中表AAAA,,,,,LLA(i,j)k01kn
k示从顶点到顶点v的路径上所经过的顶点序号不大于的最短路径长度。 vji
计算时用迭代公式:
A(i,j),min(A(i,j),A(i,k)，A(k,j)) kk,1k,1k,1
k是迭代次数，。 ijkn,,1,2,,,L
k,n最后，当A时，即是各顶点之间的最短通路值。 n
例 某公司在六个城市中有分公司，从到的直接航程票价记在下述矩cccc,,,Lcji126
阵的位置上。(表示无直接航路)，请帮助该公司设计一张任意两个城市间的票价最(i,j),
便宜的路线图。
050,402510，，
,,5001520,25,,
,1501020,,, ,,40201001025,,
,,25,2010055
,,1025,25550，，
矩阵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
浙公网安备 33021202002483