最短路径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
显示全部