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

《Floyd算法 计算最短距离矩阵和路由矩阵 查询最短距离和路由 matlab实验报告.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、求得W(k-1)和R(k-1)，依据下面的迭代求W(k)和R(k)F2：若k≤n，重复F1；若k>n，终止。>三、实验内容1、用MATLAB仿真工具实现Floyd算法：给定图G及其边(i,j)的权wi,j(1≤i≤n,1≤j≤n)，求出其各个端点之间的最小距离以及路由。（1）尽可能用M函数分别实现算法的关键部分，用M脚本来进行算法结果验证；（2）分别用以下两个初始距离矩阵表示的图进行算法验证：分别求出W(7)和R(7)。2、根据最短路由矩阵查询任意两点间的最短距离和路由（1）最短距离可以从最短距离矩阵的ω(i,j)中直接得出；（2）相应的路由则可以

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

4、ngth(w);x=w;r=zeros(n,1);%路由矩阵的初始化fori=1:1:nforj=1:1:nifx(i,j)==infr(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),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)

5、,j);endendendend;【func2.m】function[Pu]=func2(w,k1,k2)n=length(w);U=w;m=1;whilem<=nfori=1:n;forj=1:n;ifU(i,j)>U(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,n)*100;kk=k2;whilekk~=k1fori=1:nV(1,i)=U(k1,kk)-w(i,kk);ifV(1,i)==U(k

6、1,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;100100010010041.5;1.2510006.7100100;9.21001006.7015.6100;1003.1410015.60100;0.521.51001001000];w2=[00.521.5100100100;0.50100

7、1001.29.2100;2100010051003.1;1.510010001001004;1001.2510006.7100;1009.21001006.7015.6;1001003.1410015.60];[W1R1]=func1(w1)[W2R2]=func1(w2)【m2.m】w=input('输入权值矩阵w=');k1=input('输入端点1:k1=');k2=input('输入端点2:k2=');w[WR]=func1(w)[Pu]=func4(w,k1,k2);disp(['k1、k2间最短路：',num2str(P)]);dis

8、p(['k1、k2间最短距离：',num2str(u)]);五、数据结构1.主要函数最短距离、路由函数：function[