Floyd算法计算最短距离矩阵和路由矩阵查询最短距离和路由matlab实验报告

1、实验四：Floyd 算法、实验目的利用MATLAB实现Floyd算法，可对输入的邻接距离矩阵计算图中任意 两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。、实验原理Floyd算法适用于求解网络中的任意两点间的最短路径：通过图的权值矩阵 求出任意两点间的最短距离矩阵和路由矩阵。优点是容易理解，可以算出任意两 个节点之间最短距离的算法，且程序容易实现，缺点是复杂度达到，不适合计算 大量数据。Floyd算法可描述如下: 给定图G及其边(i , j )的权wi, j (1 <i<n ,1 <j <n)F0:初始化距离矩阵 W（0）和路由矩阵R（°）

2、。其中:%若叨E f有边） 丁若务任E 无边）若匸/ （对用线元索）F1：已求得W（k-1）和R（k-1），依据下面的迭代求W（k）和R（k）噹二1何（屹7就T *賊穿）F2 :若kwn,重复F1;若k>n，终止。三、实验内容1、用MATLAB仿真工具实现Floyd算法：给定图G及其边（i , j ）的权wi , j (1 <i<n ,1 <j<n)，求出其各个端点之间的最小距离以及路由。(1) 尽可能用M函数分别实现算法的关键部分，用 M脚本来进行算法结果验证;(2)分别用以下两个初始距离矩阵表示的图进行算法验证:Q 100 100 1.2 9.2 100 0.

3、5 "1000 100 5 1003.1 2100 100 0 100 1004 1.50 0.5 2 1.5 100 100 10010.5 0 100 100 1.2 9.2 1002 100 0 100 5 100 3,1L2 5 100 O6J 100 100护=1.5 100 1000 100 100 49.2 100 100'6.7 0 15.6 100100 1.2 5 100 0' 6.7 100100 3.1 4 100 15.6 0 100100 9.2 100 100 6.7 0 15.60.5 2 L5 100 100 100 0100 100

4、 3J 4 100 15,6 0 J分别求出 W(7)和R(7)。2、根据最短路由矩阵查询任意两点间的最短距离和路由(1)最短距离可以从最短距离矩阵的9(i,j)中直接得出;(2) 相应的路由则可以通过在路由矩阵中查找得出。由于该程序中使用的是前向矩阵，因此在查找的过程中，路由矩阵中r(i,j)对应的值为Vi到Vj路由上的下一个端点，这样再代入r(r(i,j),j)，可得到下下个端点，由此不断循环下去，即可找到最终 的路由。(3) 对图1，分别以端点对V4和V6, V3和V4为例，求其最短距离和路由；对 图2，分别以端点对V1和V7，V3和V5，V1和V6为例，求其最短距离和路由。3、输入一邻

5、接权值矩阵，求解最短距离和路由矩阵，及某些点间的最短路径。四、采用的语言MatLab源代码:【func1.m 】fun ctio n w r = fun c1(w)n=le ngth(w);x = w;r = zeros(n,1);% 路由矩阵的初始化for i=1:1:nfor j=1:1:nif x(i,j)=infr(i,j)=O;elser(i,j)=j;end.endend;%迭代求出k次w值for k=1: na=w;s = w;for i=1:nfor j=1: nw(i,j)=mi n( s(i,j),s(i,k)+s(k,j);end%根据k-1次值和k次w值求出k次r值 f

6、or i=1:nfor j=1: nif i=jr(i,j)=O;elseif w(i,j)<a(i,j)r(i,j)=r(i,k);elser(i,j)=r(i,j)；endendendend;【func2.m 】fun ctio n P u=fu nc2(w,k1,k2)n = len gth(w);U = w;m = 1;while m <= nfor i = 1:n;for j = 1:n;U(i,j) = U(i,m) + U(m,j);endendend m = m + 1;endu = U(k1,k2);P1=zeros(1, n);k = 1;P 1(k) = k2

7、;V = on es(1, n) * 100;kk = k2;while kk=k1for i = 1:nV(1,i) = U(k1,kk) - w(i,kk);if V(1,i) = U(k1,i)P 1(k+1)=i;kk=i;k=k+1;endendk=1;wrow = find(P 1=0);for j=le ngth(wrow):(-1):1P(k) = P1(wrow(j);k=k+1;endP；【m1.m】w1=0 100 100 1.2 9.2 100 0.5;100 0 100 5 100 3.1 2;100 100 0 100 100 4 1.5;1.2 5 100 0 6

8、.7 100 100;9.2 100 100 6.7 0 15.6 100;100 3.1 4 100 15.6 0 100;0.5 2 1.5 100 100 100 0;w2=0 0.5 2 1.5 100 100 100;0.5 0 100 100 1.2 9.2 100;2 100 0 100 5 100 3.1;r = zeros( n,1);%路由矩阵的初始化1.5 100 100 0 100 100 4;100 1.2 5 100 0 6.7 100;100 9.2 100 100 6.7 0 15.6;100 100 3.1 4 100 15.6 0;W1 R1 = fun c

9、1(w1)W2 R2 = fun c1(w2)【m2.m】for j=1:nw=i nput('输入权值矩阵w=');k1=i nput('输入端点1:k1=');k2=i nput('输入端点2:k2=');W R = fun c1(w)P u=fu nc2(w,k1,k2);disp('k1、k2 间最短路：,num2str(P);disp('k1、k2 间最短距离：,num2str(u);五、数据结构1.主要函数最短距离、路由函数:fun cti on w r = fun c1(w) n=le ngth(w);for i=1

10、:1:nfor j=1:1:nif x(i,j)=100r(i,j)=0；elser(i,j)=j；end,end end;%迭代求岀k次w值 for k=1: na=w;s = w;for i=1: nfor j=1:nw(i,j)=mi n( s(i,j),s(i,k)+s(k,j);endend%根据k-1次值和k次w值求岀k次r值for i=1: nif i=jr(i,j)=O;elseif w(i,j)va(i,j)r(i,j)=r(i,k);elser(i,j)=r(i,j)；endendend end;最短路径函数:fun ctio n P u=fu nc2(w,k1,k2) n

11、 = len gth(w);U = w;m = 1;while m <= nfor i = 1:n;forj = 1:n;U(i,j) = U(i,m) + U(m,j);endendendm = m + 1;end u = U(k1,k2);P1=zeros(1, n);k = 1;P1(k) = k2;V = on es(1, n) * 100;kk = k2;while kk=k1for i = 1:nV(1,i) = U(k1,kk) - w(i,kk);if V(1,i) = U(k1,i)P1(k+1)=i;kk=i;k=k+1;endend end k=1;wrow = f

12、in d(P1=0);for j=le ngth(wrow):(-1):1P(k) = P1(wrow®);k=k+1;endP；2.算法的流程图Floyd算法:II 结束六、实验结论与分析Cornnnand Windown.1W102. 50002. 00001.20007.&0005.SOOOO.SOOO2. 500003-50003. 700010*40003.10002-00001 OCO'O3. 500003.20009.90004.00001.E00OL 2C003.70003. 200000*7000S.30001.7000二 900010. 40009

13、.90006.7000013.50008.40005,0003* 0004- 00006.S00013*500005" 1000仇 50002. 00001.EOOO1.70003. 40005.10000R11420通过上图可知,V4V6之间最短距离是6.8，最短路由是 V4 >V1 >V7>V2 >V6,3和V4之间最短距离是3.2，最短路由是V3 >V7 >V1 >V4Cornftiand Window¥200.50003. OOOO1.50fl01, VOCOS, 40005.10000.500002. 50002.0000

14、L 20IC07- 90005.SOOO2.00002.500003.甜前3. 70010. 40003. 10001.50002.0000玄 500003- 2000乳 90004.00001.70001.20003. 70003. 20()006. 70006. 3000S.40007.900010.40009.90006, ；0<30013.50005.10005.eooo3. 10004.00006. SOflO13. 50000E20254通过上图可知,，点对V1V7之间最短距离是5.1，最短路由是V1 >V3端点对V1和V6之间最短距离是8.4，最短路由是V1 >

15、V2 >V5 >V6>V7端点对V3和V5之间最短距离是3.7,最短路由是V3 >V1 >V2 >V5» 2tt.兀収酋駆降*=0 inf inf 5 inffe汕端点l；Jtl=rinf irf 0 3 irf Lnf Lnf .inf 9 15 4 fli 15 4 inf 0 inf iirf; inf irrf lO :nf 0V 二0 InLLnf吕In£:nfInf03InfInf：n£hi!3015e&4Inf0Inf:nfInf Inf10Lif:nfTn-fInf12InfInfCt -0审12b*bIS26ISJ1ft1c2350151e3i70u13：3 310；5niLA352112n 一