Floyd算法计算最短距离矩阵和路由矩阵查询最短距离和路由matlab实验报告Word文档下载推荐.docx
《Floyd算法计算最短距离矩阵和路由矩阵查询最短距离和路由matlab实验报告Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《Floyd算法计算最短距离矩阵和路由矩阵查询最短距离和路由matlab实验报告Word文档下载推荐.docx（13页珍藏版）》请在冰点文库上搜索。
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）相应的路由则可以通过在路由矩阵中查找得出。
由于该程序中使用的是前向矩阵，因此在查找的过程中，路由矩阵中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=length（w）;
x=w;
r=zeros（n,1）;
%路由矩阵的初始化
fori=1:
1:
n
forj=1:
ifx（i,j）==inf
r（i,j）=0;
else
r（i,j）=j;
end,
end
end;
%迭代求出k次w值
fork=1:
a=w;
s=w;
fori=1:
w（i,j）=min（s（i,j）,s（i,k）+s（k,j））;
%根据k-1次值和k次w值求出k次r值
ifi==j
elseifw（i,j）<
a（i,j）
r（i,j）=r（i,k）;
r（i,j）=r（i,j）;
【func2.m】
function[Pu]=func2（w,k1,k2）
n=length（w）;
U=w;
m=1;
whilem<
=n
fori=1:
n;
forj=1:
ifU（i,j）>
U（i,m）+U（m,j）
U（i,j）=U（i,m）+U（m,j）;
m=m+1;
end
u=U（k1,k2）;
P1=zeros（1,n）;
k=1;
P1（k）=k2;
V=ones（1,n）*100;
kk=k2;
whilekk~=k1
V（1,i）=U（k1,kk）-w（i,kk）;
ifV（1,i）==U（k1,i）
P1（k+1）=i;
kk=i;
k=k+1;
k=1;
wrow=find（P1~=0）;
forj=length（wrow）:
（-1）:
1
P（k）=P1（wrow（j））;
P;
【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.501001001.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]=func2（w,k1,k2）;
disp（['
k1、k2间最短路：
'
num2str（P）]）;
k1、k2间最短距离：
num2str（u）]）;
五、数据结构
1.主要函数
最短距离、路由函数：
ifx（i,j）==100
最短路径函数：
2.算法的流程图
Floyd算法：
结束
开始
Wi,j（k）=min（Wi,j（k-1）,Wik（k-1）+Wkj（k-1））
n=length（w）
k=0
k≤n?
Wi,j（k）<
Wi,j（k-1）?
Wi,j（k）≤Wi,j（k-1）?
Yes
ri,j（k）=ri,j（k-1）
No
ri,j（k）=ri,k（k-1）
六、实验结论与分析
通过上图可知，V4和V6之间最短距离是6.8，最短路由是V4—>
V1—>
V7—>
V2—>
V6，3和V4之间最短距离是3.2，最短路由是V3—>
V4
通过上图可知，，点对V1和V7之间最短距离是5.1，最短路由是V1—>
V3—>
V7
端点对V3和V5之间最短距离是3.7，最短路由是V3—>
V5
端点对V1和V6之间最短距离是8.4，最短路由是V1—>
V5—>
V6
七、遇到的问题及解决方法
（1）图的等价表示方法；
（2）两点间的最短路径查询算法。
八、实验心得
通过本次实验实现了用计算机语言编写Floys本掌握了算法的实现方法，对MatLab编程语言更加熟悉，培养了算法设计与优化能力。
此次实验我受益匪浅。
升级会员 