最短路径matlab计算机仿真

计算机仿真期末作业姓名：吴隐奎班级：04601学号：041751日期：2007-6-15题目：Floyd算法实现和分析内容：用MATLAB仿真工具实现Floyd算法，求任意两端间的最短路径。要求：尽可能用M函数分别实现算法的关键部分，用M脚本来进行算法结果验证；分别用以下两个图（用初始距离矩阵表示）进行算法验证：-01001001.29.21000.5_图一：W⑼=|0.521.51001001000]_-00.521.5100100100-图二：W（o）=L1001003.1410015.60算法：给定图g及其边色力的权卬（l<z<n,l<j<n）F0：初始化距离矩阵W（。）和路由矩阵R。）。其中：w若ewE（有边）卬（0）=<00若e纪E（无边）ij0若i=j（对角线元素）。）=[j若'0,其它Fl：已求得和Rbi）,依据下面的迭代求W伙）和R伙）w（k）=min（w-i）,卬伏-i）+卬伏川）i,ji,ji,kk,jr(j)若w伏)<w(*-1)r(Jt)=i,k什i,ji.ji.jr(Jt-1)右卬(k)=W(2-1)Iiji，ji，jF2：若k<n,重复F1；若k=n,终止。仿真：用四个m文件来实现仿真，其中main为主函数，首先测试出矩阵的长度，然后赋给n,作为循环的次数；然后调用fund实现路由矩阵的初始化，把第k-1次的值付给a后，调用func2函数来迭代求出k次的w值，调用func3函数，根据a(实际上为k-1次w值)值和k次w值来求出k次r值。迭代循环n次。主要程序：n=length(w);refund(w,n);fork=l:na=w;w=func2(w,n,k);r=func3(a,w,r,n,k);end;Fund实现路由矩阵的初始化主要程序fori=l:1:nforj=l:1:nifx(i,j)==100rO(i,j)=0;elserO(i,j)=j;end,end;end;Iruuc2该函数实现的功能是根据k-1次w的值迭代求k次w的值主要程序fori=l:nforj=l:nw(i,j)=min(s(i,j),s(i,k)+s(k,j));endendFunc3来根据k-1次w值和k次w值的大小求k次R的值主要程序：fori=l:nforj=l:nifi==jr(i,j)=0;elseifw(i,j)<a(i,j)r(i,j)=r(i,k);

elser(i,j)=r(i,j);endendend结果：图一的结果：w=02.50002.00001.20007.90005.60000.50002.500003.50003.700010.4()003.10002.00002.00003.500003.20009.90004.00001.50001.20003.70003.200006.70006.80001.70007.900010.40009.90006.7000013.50008.40005.60003.10004.00006.800013.500005.10000.50002.00001.50001.70008.40005.10000r=0774477707776777077671110511444404422322021231120可以看出：V4和V6之间最短距离是6.8,最短路由是V4—>V1—>V7—>V2—>V6V3和V4之间最短距离是3.2,最短路由是V3—>V7—>V1—>V4图二的结果：w=00.50002.00001.50001.70008.40005.10000.500002.50002.00001.20007.90005.60002.00002.500003.50003.700010.40003.10001.50002.00003.500003.20009.90004.00001.70001.20003.70003.200006.70006.80008.40007.900010.40009.90006.7000013.50005.10005.60003.10004.00006.800013.50000r二0234223101155111011171110117222206255555053334330端点对V1和V7之间最短距离是5.1,最短路由是V1—>V3—>V7端点对V3和V5之间最短距离是3.7,最短路由是V3—>V1—>V2—>V5端点对V1和V6之间最短距离是8.4,最短路由是V1—>V2—>V5—>V6总结：通过一个学期计算机仿真课的学习，我现在已经能很熟练的使用的仿真工具matlab来进行