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

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

2、其它|F1:已求得 W（k-1）和 R（k-1）,依据下面的迭代求 W 的和 R 的吧二皿1（唠？喈+啕）网伊若叫产“产七一反心若明产二“严F2：若 kn,终止。三、实验内容1、用MATLAB仿真工具实现Floyd算法：给定图G及其边（i,j）的权Wi,j（1W由，1可f），求出其各个端点之间的最小距离以及路由。（1）尽可能用M函数分别实现算法的关键部分，用M脚本来进行算法结果验证；（2）分别用以下两个初始距离矩阵表示的图进行算法验证：分别求出W和R(7)2、根据最短路由矩阵查询任意两点间的最短距离和路由(1)最短距离可以从最短距离矩阵的 3(i,j)中直接得出；(2)相应的路由则可以通过在路

3、由矩阵中查找得出。由于该程序中使用的是前向矩阵，因此在查找的过程中，路由矩阵中 r(i,j)对应的值为 Vi 到 Vj 路由上的下一个端点，这样再代入r(r(i,j),j),可得到下下个端点，由此不断循环下去，即可找到最终的路I(3)对图 1,分别以端点对 V4 和 V6,V3 和 V4 为例，求其最短距离和路由；对图 2,分别以端点对 V1 和 V7,V3 和 V5,V1 和 V6 为例，求其最短距离和路由。3、输入一邻接权值矩阵，求解最短距离和路由矩阵，及某些点间的最短路径。四、采用的语言MatLab源代码：func1.mfunctionwr=func1(w)n=length(w);x=w

4、;r=zeros(n,1);%汕矩阵的初始化fori=1:1:nforj=1:1:nifx(i,j)=infr(i,j)=O;elser(i,j尸j；end,endend;%迭代求出k次w值fork=1:na=w;s=w;fori=1:nforj=1:nw(i,j)=min(s(i,j),s(i,k)+s(k,j);end0100100L29.210005100010051003.12100100010010041.5用=1.2510006.71001009.21001006.7015.61001003.1410015.601000521.5100100100000.521.510010010

5、00.50100100L29.21002100010051003,11.5100100010010041001251000651001009.21001006.7015.61001003.1410015,60end%根据k-1次值和k次w值求出k次r值fori=1:nforj=1:nifi=jr(i,j)=0;elseifw(i,j)a(i,j)r(i,j)=r(i,k);elser(i,j)=r(i,j);endendendend;func2.mfunctionPu=func2(w,k1,k2)n=length(w);U=w;m=1;whilemU(i,m)+U(m,j)U(i,j)=U(i

6、,m)+U(m,j);endendendm=m+1;endu=U(k1,k2);P1=zeros(1,n);k=1;P1(k)=k2;V=ones(1,n)*100;kk=k2;whilekk=k1fori=1:nV(1,i)=U(k1,kk)-w(i,kk);ifV(1,i)=U(k1,i)P1(k+1)=i;kk=i;k=k+1;endendendk=1;wrow=find(P1=0);forj=length(wrow):(-1):1P(k)=P1(wrow(j);k=k+1;endP;【m1.m】w1=01001001.29.21000.5;100010051003.12;1001000

7、10010041.5;1.2510006.7100100;9.21001006.7015.6100;1003.1410015.60100;0.521.51001001000;w2=00.521.5100100100;0.501001001.29.2100;2100010051003.1;1.510010001001004;1001.2510006.7100;1009.21001006.7015.6;1001003.1410015.60;W1R1=func1(w1)W2R2=func1(w2)m2.mw=input(输入权值矩阵w=);k1=input(输入端点1:k1=);k2=input(输

8、入端点2:k2=);WR=func1(w)Pu=func2(w,k1,k2);disp(k1、k2间最短路：,num2str(P);disp(k1、k2间最短距离：,num2str(u);五、数据结构1.主要函数最短距离、路由函数：functionwr=func1(w)n=length(w);x=w;r=zeros(n,1);%路由矩阵的初始化fori=1:1:nforj=1:1:nifx(i,j)=100r(i,j)=0;elser(i,j)=j;end,endend;%迭代求出 k 次 w 值fork=1:na=w;s=w;fori=1:nforj=1:nw(i,j)=min(s(i,j)

9、,s(i,k)+s(k,j);endend%根据 k-1 次值和 k 次 w 值求出 k 次 r 值 fori=1:nforj=1:nifi=jr(i,j)=0;elseifw(i,j)a(i,j)r(i,j)=r(i,k);elser(i,j)=r(i,j);endendendend;最短路径函数：functionPu=func2(w,k1,k2)n=length(w);U=w;m=1;whilemU(i,m)+U(m,j)U(i,j)=U(i,m)+U(m,j);endendendm=m+1;endu=U(k1,k2);P1=zeros(1,n);k=1;P1(k)=k2;V=ones(1

10、,n)*100;kk=k2;whilekk=k1fori=1:nV(1,i)=U(k1,kk)-w(i,kk);ifV(1,i)=U(k1,i)P1(k+1)=i;kk=i;k=k+1;endendendk=1;wrow=find(P1=0);forj=length(wrow):(-1):1P(k)=P1(wrow(j);k=k+1;endP;2.算法的流程图Floyd法：开始六、实验结论与分析nlW1=02.50002.00001.20007.90005.60000.50002.500003.50003-700010.40003.10002,00002,00003.5000Q3.20009,

11、90004,00001.5000L20003.70003.200006.70006.80001.70007.&00010.40009.900。6.7000013.50008.40005.50003*10004,00006.800013,500005.10000.50002.00001.5000L70003.40005-10000Rl=0144j:0ii6i40j511I05I144i40&422322021231120通过上图可知，V4和V6之间最短距离是6.8,最短路由是V4V1V7V2V6,3和V4之间最短距离是3.2,最短路由是V3-V7-V1V400.50002.000

12、01.50001.7000S.40005.10000.500002.50002.00001.20007.90005.60002.00002.500003.50003.700010.40001000L60002.00003,500003.2000仇9000工L70001.20003.70003.200006.70006.300Q8.40007.900010.4000g.9Q0。6.7000013.50005.1000S.60003.10004.00006.MOOL3.50000R2=02342231011551110I11711I0II7222206255555053334330fii通过上图可知，点对V1和V7之间最短距离是5.1,最短路由是V1V3-V7端点对V3和V5之间最短距离是3.7,最短路由是V3-V1V2V5端点对V1和V6之间最短距离是8.4,最短路由是V1V2V5-V6CommandWindow2输入权值矩时 infinf5infinf,inf03infirtfinf.tnf901546.84inf0nfinf.infinf10inf0箱入端点 l:k】=2输入端点受 k2M60312516IS2603IEg23g01546g4Q1113