实验一：路径选择实验
一、实验目的
在进行通信网选择路由时，首选路由和各个迂回路由通常都是按照路径最短的原则进行的，目的是为了使网络费用达到最小。在求解最短径的算法中常用的有D算法和F算法。D算法用于求指定节点到其他各节点的最短路径；F算法用于求任意端间最短径。在实际中都是由计算机实现这两种算法来帮助设计人员进行路由设计。本次实验目的就是要使学生深入理解这两种算法并能用计算机实现这两种算法。
二、实验内容
用编程语言实现F算法。
F算法M文件内容如下：
function [w,r]=fsuanfa(m)
% F算法的函数文件
v_num=size(m);
v_num=v_num(1);
w=zeros(v_num);
r=zeros(v_num);
for i=1:v_num
for j=1:v_num
if i~=j
if(m(i,j)==0)
w(i,j)=inf;
else
w(i,j)=m(i,j);
r(i,j)=j;
end
end
end
end
disp W0=
disp(w)
disp R0=
disp(r)
for k=1:v_num
pause;
for i=1:v_num
if(i~=k)
for j=1:v_num
if(w(i,k)+w(k,j)w(i,j)=w(i,k)+w(k,j);
r(i,j)=k;
end
end
end
end
fprintf('W%d=\n',k);
disp(w)
fprintf('R%d=\n',k);
disp(r)
end
%r=m./2;
end
三、实验结果
把fsuanfa .m添加到MATLAB的当前目录下，在MA TLAB的command window下运行：
lj=[0 2 8 1 0 0 0 0
2 0 6 0 1 0 0 0
8 6 0 7 5 1 2 0
1 0 7 0 0 0 9 0
0 1 5 0 0 3 0 8
0 0 1 0 3 0 4 6
0 0 2 9 0 4 0 3
0 0 0 0 8 6 3 0];
Fsuanfa(lj);
可得到如下结果：
W0=
0 2 8 1 Inf Inf Inf Inf
2 0 6 Inf 1 Inf Inf Inf
8 6 0 7 5 1 2 Inf
1 Inf 7 0 Inf Inf 9 Inf
Inf 1 5 Inf 0 3 Inf 8
Inf Inf 1 Inf 3 0 4 6
Inf Inf 2 9 Inf 4 0 3
Inf Inf Inf Inf 8 6 3 0 R0=
0 2 3 4 0 0 0 0
1 0 3 0 5 0 0 0
1 2 0 4 5 6 7 0
1 0 3 0 0 0 7 0
0 2 3 0 0 6 0 8
0 0 3 0 5 0 7 8
0 0 3 4 0 6 0 8
0 0 0 0 5 6 7 0
W1=
0 2 8 1 Inf Inf Inf Inf
2 0 6
3 1 Inf Inf Inf
8 6 0 7 5 1 2 Inf
1 3 7 0 Inf Inf 9 Inf
Inf 1 5 Inf 0 3 Inf 8
Inf Inf 1 Inf 3 0 4 6
Inf Inf 2 9 Inf 4 0 3
Inf Inf Inf Inf 8 6 3 0 R1=
0 2 3 4 0 0 0 0
1 0 3 1 5 0 0 0
1 2 0 4 5 6 7 0
1 1 3 0 0 0 7 0
0 2 3 0 0 6 0 8
0 0 3 0 5 0 7 8
0 0 3 4 0 6 0 8
0 0 0 0 5 6 7 0
W2=
0 2 8 1 3 Inf Inf Inf
2 0 6
3 1 Inf Inf Inf
8 6 0 7 5 1 2 Inf
1 3 7 0 4 Inf 9 Inf
3 1 5
4 0 3 Inf 8
Inf Inf 1 Inf 3 0 4 6
Inf Inf 2 9 Inf 4 0 3
Inf Inf Inf Inf 8 6 3 0 R2=
0 2 3 4 2 0 0 0
1 0 3 1 5 0 0 0
1 2 0 4 5 6 7 0
1 1 3 0
2 0 7 0
2 2
3 2 0 6 0 8
0 0 3 0 5 0 7 8
0 0 3 4 0 6 0 8
0 0 0 0 5 6 7 0
W3=
0 2 8 1 3 9 10 Inf
2 0 6
3 1 7 8 Inf
8 6 0 7 5 1 2 Inf
1 3 7 0 4 8 9 Inf
3 1 5
4 0 3 7 8
9 7 1 8 3 0 3 6
10 8 2 9 7 3 0 3
Inf Inf Inf Inf 8 6 3 0 R3=
0 2 3 4 2 3 3 0
1 0 3 1 5 3 3 0
1 2 0 4 5 6 7 0
1 1 3 0
2
3 7 0
2 2
3 2 0 6 3 8
3 3 3 3 5 0 3 8
3 3 3
4 3 3 0 8
0 0 0 0 5 6 7 0
W4=
0 2 8 1 3 9 10 Inf
2 0 6
3 1 7 8 Inf
8 6 0 7 5 1 2 Inf
1 3 7 0 4 8 9 Inf
3 1 5
4 0 3 7 8
9 7 1 8 3 0 3 6
10 8 2 9 7 3 0 3
Inf Inf Inf Inf 8 6 3 0 R4=
0 2 3 4 2 3 3 0
1 0 3 1 5 3 3 0
1 2 0 4 5 6 7 0
1 1 3 0
2
3 7 0
2 2
3 2 0 6 3 8
3 3 3 3 5 0 3 8
3 3 3
4 3 3 0 8
0 0 0 0 5 6 7 0
