最短路径matlab计算机仿真.doc

计算机仿真期末作业 姓名：吴隐奎 班级：04601 学号：041751 日期：2007-6-15 题目：Floyd算法实现和分析 内容：用MATLAB仿真工具实现Floyd算法，求任意两端间的最短路径。 要求：尽可能用M函数分别实现算法的关键部分，用M脚本来进行算法结果验证；分别用以下两个图（用初始距离矩阵表示）进行算法验证： 图一： 图二： 算法：给定图及其边的权 F0：初始化距离矩阵和路由矩阵。其中： F1：已求得和，依据下面的迭代求和 F2：若kn，重复F1；若k=n，终止。 仿真： 用四个m文件来实现仿真，其中main为主函数，首先测试出矩阵的长度，然后赋给n，作为循环的次数；然后调用func1实现路由矩阵的初始化，把第k-1次的值付给a 后，调用func2函数来迭代求出k次的w值，调用func3函数，根据a（实际上为k-1次w值）值和k次w值来求出k次r值。迭代循环n次。 主要程序: n=length(w); r=func1(w,n); for k=1:n a=w; w=func2(w,n,k); r=func3(a,w,r,n,k); end; Func1实现路由矩阵的初始化 主要程序 for i=1:1:n for j=1:1:n if x(i,j)==100 r0(i,j)=0; else r0(i,j)=j; end, end; end; Fuuc2该函数实现的功能是根据k-1次w的值迭代求k次w的值 主要程序 for i=1:n for j=1:n w(i,j)=min(s(i,j),s(i,k)+s(k,j)); end end Func3来根据k-1次w值和k次w值的大小求k次R的值 主要程序： for i=1:n for j=1:n if i==j r(i,j)=0; elseif w(i,j)a(i,j) r(i,j)=r(i,k); else r(i,j)=r(i,j); end end end 结果： 图一的结果： w= 0 2.5000 2.0000 1.2000 7.9000 5.6000 0.5000 2.5000 0 3.5000 3.7000 10.4000 3.1000 2.0000 2.0000 3.5000 0 3.2000 9.9000 4.0000 1.5000 1.2000 3.7000 3.2000 0 6.7000 6.8000 1.7000 7.9000 10.4000 9.9000 6.7000 0 13.5000 8.4000 5.6000 3.1000 4.0000 6.8000 13.5000 0 5.1000 0.5000 2.0000 1.5000 1.7000 8.4000 5.1000 0 r= 0 7 7 4 4 7 7 7 0 7 7 7 6 7 7 7 0 7 7 6 7 1 1 1 0 5 1 1 4 4 4 4 0 4 4 2 2 3 2 2 0 2 1 2 3