北邮信息工程通信网理论基础实验4报告

1、信息与通信工程学院通信网理论基础实验报告班级：姓名：学号:实验四 Floyd算法一、实验目的Floyd算法通过图的权值矩阵求出任意两点间的最短距离矩阵和路由矩阵。 优点是容易理解，可以算出任意两个节点之间最短距离的算法，且程序容易实 现，缺点是复杂度达到，不适合计算大量数据。本次实验要求利用MATLAB实现Floyd算法，可对输入的邻接距离矩阵计 算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距 离和路由。实验原理Floyd算法可描述如下：给定图G及其边(i, j)的权w j (仁i兰n,仁j兰n)F0:初始化距离矩阵W和路由矩阵R(0)。其中:'Wj若e乏e (有

2、边) Wj(0)=三若 er' E (无边)0 若i = j (对角线元素)r?0)j若Wjj八0,其它F1:已求得W(k-1)和R(k-1)，依据下面的迭代求 W(k)和R(k)w(k)i,J=mi narw："0 +wk；-1)(k)ri,j'(k书ri,kPi,j(k4)(k)(k -4)若 wi,j: wj,j(k)若 wi,jw,jF2:若k空n ,重复F1;若k n，终止三、实验内容用MATLAB 仿真工具实现Floyd算法：给定图G及其边（i ,j ）的权Wjj（1兰i wn , 1 j兰n，求出其各个端点之间的最小距离以及路由 1、分别用以下两个初始距

3、离矩阵表示的图进行算法验证:0 100 100 1.2 9.2 100 0.5 100 0 100 5 100 3.1 2 100 100 0 100 100 4 1.5W(0) = 1.2 5 100 0 6.7 100 1009.2 100 100 6.7 0 15.6 100100 3.1 4 100 15.6 0 100'0.5 2 1.5 100 100 100 0|_0 0.5 2 1.5 100 100 100 0.5 0 100 100 1.2 9.2 100I2 100 0 100 5 100 3.1W(0) = 1.5 100 100 0 100 100 4100

4、1.2 5 100 0 6.7 100100 9.2 100 100 6.7 0 15.6100 100 3.1 4 100 15.6 0分别求出W和R2、根据最短路由矩阵查询任意两点间的最短距离和路由（1） 最短距离可以从最短距离矩阵的'i, j中直接得出；（2）相应的路由则可以通过在路由矩阵中查找得出。由于该程序中使用的是前向矩阵，因此在查找的过程中，路由矩阵中r（i,j）对应的值为Vi到Vj路由上的下一个端点，这样再代入r（r（i,j）,j），可得到下下个端点，由此不断循环下 去，即可找到最终的路由。（3）对图1,分别以端点对V4和V6, V3和V4为例，求其最短距离和路 由；对

5、图2,分别以端点对V1和V7, V3和V5，V1和V6为例，求其最短距 离和路由。3、输入一邻接权值矩阵，求解最短距离和路由矩阵，及某些点间的最短路径。4、扩展的实验内容（选作部分）（1）实现Floyd算法的回溯路由矩阵；（2）探讨可降低算法复杂度的算法。四、程序基本信息1设计语言及开发工具：MATLAB。2、数据结构：本次实验涉及到了数据结构中图的相关内容，如图的遍历等等。另外，实 验中采用不定长数组存储算法的相关矩阵信息。3、主要函数(算法)：本程序采用MATLAB语言编写，程序文件名为Floyd.m。第一部分：Floyd算法求出其各个端点之间的最小距离以及路由这里包含两种路由方法的Flo

6、yd算法：前向路由和回溯路由。下面先介绍 其中的前向路由方法部分。它的主要思想及流程在实验原理部分已给出，下页 以流程图的形式给出该段程序的工作流程，和原算法本身相比并无太多不同。回溯路由方法的Floyd算法流程如下：F0:初始化距离矩阵W和路由矩阵R(0)。其中：” Wj 若ej e (有边)Wj(0)若 er E (无边)0 若i = j (对角线元素)r?0)i 若 w ij (0)=:0 ,其它F1:已求得W(k-1)和R(k-1)，依据下面的迭代求 W(k)和R(k)(k)w,j=mi n(w(，k)(kJ) ,Wi,k(k-1) k, j(k) r,j(k书 rk,j若 wi,j(

7、k):wi,j(k J)(kJ) ri,j(k)(kJ)若 wi,j=w,jF2:若k乞n ,重复F1;若k n，终止。可见该算法仅在路由矩阵更新方面有些许不同，因此这里不再给出它的流 程图。另外要说明的一点是，程序中 二无法表示，用100代替。结束Floyd算法（前向路由）流程图第二部分：Floyd算法程序改进Floyd算法中，距离矩阵每次更新的元素非常少（相对于矩阵元素总个数而 言），而路由矩阵又随着距离矩阵的更新而更新。原先的程序中无论是否更新 都要执行一次赋值操作，其实只需要保留需要更新值的赋值操作，不更新值的 赋值操作没有意义。因此优化后的程序可以大大减少赋值次数。这个程序其实 没有

8、改变原算法思想，只是针对程序本身进行了优化。第三部分：查询任意两点间的最短距离和路由这段算法非常简单，主要利用了 Floyd算法生成的距离矩阵和路由矩阵， 以下简述它的工作流程：开始输入源端点i 和目的端点j返回距离矩 阵位置为（i,j） 的元素值即最短距离查询路由矩阵 中位置为（i,j） 的元素值记录查询到的 值，并将其赋给i按顺序返 回以上查 询到的值*结束五、程序运行结果与分析1、禾I用给定的两个路由矩阵判定算法正确性:0 100 100 1.2 9.2 100 0.5100 0 100 5 100 3.1 2100 100 0 100 100 4 1.5W(°)= 1.2 5

9、 100 0 6.7 100 100 W9.2 100 100 6.7 0 15.6 100100 3.1 4 100 15.6 0 100J3.5 2 1.5 100 100 100 00 0.5 2 1.5 100 100 1000.5 0 100 100 1.2 9.2 1002 100 0 100 5 100 3.1=1.5 100 100 0 100 100 4100 1.2 5 100 0 6.7 100100 9.2 100 100 6.7 0 15.6100 100 3.1 4 100 15.6 0 一矩阵1的执行结果:WL =02.SOOQ2. 00001,20007. 90

10、005. 60000. 50002.500003. 5000龙 700010. 400Q3. 10002. 00002.00003.500003.20009.90004.00001. 50001. 20003.70003.200006.70006.SOOO1.70007. 900010-40006.90006. 7000013. 50008. 40005,60003.10004. 00006.300013.500005. 10000.50002.0Q0Q1. 50001.70008. 4QOO5.10000R1 =07T0i1斗|:巧d7i0il'6i11105114444044223

11、22021231120R2 =071斗2I014227i014334ii01214号1|502176614027T71420MUPKIW FOTH AM> rtUCCIMMUMEAIICHS矩阵2的执行结果：通信网理论基础实验报告W1 =00. 50002.00001.50001. 70008. 40005.10000,500002.50002,00001. 20007. 90005* 60002. 00002. 500003. 50003.700010, 40003.10001.50002. 0000X500003* 20009. 90004. 00001. 70001. 20003.

12、 7000王 200006. 70006.30008. 40007. 900010.40009.90005.7000013.50005. 10005. 60003.10004.00006.800013. 50000阵,注：上面的运行结果中,W1为最短距离矩阵,R1为最短路由（前向）矩R2为最短路由（回溯）矩阵R102342231011551110111711011|'222206255555053334330R2 =01112532011253310125341102542511Q53251160331I'd2502、根据最短路由矩阵查询任意两点间的最短距离和路由: 以下查询均

13、使用前向最短路由矩阵。矩阵 1： V4 至U V6，V3 至U V4。要求最短距离和路由吗'Y/N) ? yi青输入源端号：4i青输入目的端号：6最短距离：6. S最短路由匸4172 6要求最短距离和路由吗f¥/N)?y请输入源端号：3i青输入目的端号：4最短距离：3, 2最短路由*3714要求最短距离和路由吗'Y/N)?即V4到V6的最短距离：6.8,最短路由：VV1V7VPV6 ;V3到V4的最短距离：3.2，最短路由：V3 V7 V1V4 。矩阵 2： V1 至U V7 , V3 至U V5, V1 至U V6。要求最短距离和路由吗(Y/N' ? y语输

14、入源端g： 1话输入目的端号：7最短距离：5- 1最短略由；13 ；要求最短距离和路由吗(Y/N' ? y请输入源端号：3语输入目的端号：5最姮距离:3. 7最短略由：3125要求最短距离和路由吗fY/N'Vy请输入源端号：1済输入目的端号：6最短距离:8, 4最短路由：1256要求最恿距离和路由吗(Y/N'?即V1到V7的最短距离：5.1，最短路由：V1 V3 V7 ;V3到V5的最短距离：3.7，最短路由：V3V1 V2 V5 ;V1到V6的最短距离：8.4，最短路由：V1 V2V5V6。3、原程序与改进后的程序运行结果及时间比较：采用矩阵1进行测试。测试时，原程序

15、的回溯矩阵处理语句被注释掉，即不让它处理回溯矩阵, 同时两个程序的初始化矩阵 W0和R0的时间都不考虑。原程序运行结果：02. 50002. 00001.20007. 90005.60000.50002.500003.50003.700010. 40003*10002.00002. 00003. 500003.20009.90004.00001. 50001.20003. 70003.200006. 7000S.8QQ01. 70007.900010. 40009. 90006.7000013.50008. 40005.60003. 10004. 00006.800013.500005.100

16、00.50002. 00001. 50001.7000S. 40005,1QQQ0R1 =0774467671144022070777770771110 5444402232212311FloydH% （未优化）执行时30- 00017451改进后程序运行结果:02.50002, 00001+20007. 90005. 6000 50002,500003.50003,7000LD. 40003. 10002. 00002.00003.500003, 20009.90004. 0000L50001,20003.70003.300006.70006. 80001. 70007. 900010. 4

17、0009. &0006. 7000013. 50008. 40005. 60003.10004. 00006,800013. 500005, 10000, 60002.0000U 500Q1,70008. 40005. 10000FloydM (优化后)执行时ii6. 073Se-0OE 要求最短距离和路由吗(Y/N) ? |这里仅给出一次运行的结果。由上图可见，两个算法的运行结果是完全相 同的（路由矩阵对角线上的元素不同，但是实际应用时对角线上的元素值没有 意义），且优化后的程序执行时间比未优化的程序短。当然，每次运行结果都 是不同的，有极小的可能会出现二者执行时间近似甚至优化后程序超过未优化 程序。由于时间所限，无法对每次的运行时间加以统计，但大致上，优化后程 序平均起来运行时间要比未