《北邮信息工程通信网理论基础实验4报告——Floyd算法》由会员分享，可在线阅读，更多相关《北邮信息工程通信网理论基础实验4报告——Floyd算法（11页珍藏版）》请在金锄头文库上搜索。
1、信息与通信工程学院信息与通信工程学院通信网理论基础实验报告通信网理论基础实验报告班班级：级： 姓姓名：名： 学学号：号： 序序号：号： 通信网理论基础实验报告第 1 页 实验四Floyd 算法一、实验目的Floyd 算法通过图的权值矩阵求出任意两点间的最短距离矩阵和路由矩阵。 优点是容易理解，可以算出任意两个节点之间最短距离的算法，且程序容易实 现，缺点是复杂度达到 ，不适合计算大量数据。本次实验要求利用 MATLAB 实现 Floyd 算法，可对输入的邻接距离矩阵计 算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距 离和路由。二、实验原理Floyd 算法可描述如下：给定图
2、及其边的权G( , )i j,(1,1)i jwinjn F0：初始化距离矩阵和路由矩阵。其中：(0)W(0)R(0)0ijijijijweEweEij 若（有边）若（无边）若(对角线元素)(0) (0)w 0,ij ijjr 若其它F1：已求得和，依据下面的迭代求和( -1)kW( -1)kR( )kW( )kR( )(1)(1)( -1) ,min(,)kkkk i ji ji kk jwwww(1)( )(1) ,( ) ,(1)( )(1) ,kkk i ki ji jk i jkkk i ji ji jrwwrrww若若F2：若，重复 F1；若，终止。knkn通信网理论基础实验报告第
3、 2 页 三、实验内容用 MATLAB 仿真工具实现 Floyd 算法：给定图及其边的权G( , )i j，求出其各个端点之间的最小距离以及路由。,(1,1)i jwinjn 1、分别用以下两个初始距离矩阵表示的图进行算法验证：(0)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.5 1.2 5 100 0 6.7 100 100 9.2 100 100 6.7 0 15.6 100 100 3.1 4 100 15.6 0 100 0.5 2 1.5 100 100 100 0W (0)0 0.5 2
4、 1.5 100 100 100 0.5 0 100 100 1.2 9.2 1002 100 0 100 5 100 3.11.5 100 100 0 100 100 4 100 1.2 5 100 0 6.7 100100 9.2 100 100 6.7 0 15.6100 100 3.1 4 100 15.6 0W 分别求出和。(7)W(7)R2、根据最短路由矩阵查询任意两点间的最短距离和路由（1）最短距离可以从最短距离矩阵的中直接得出；ji,（2） 相应的路由则可以通过在路由矩阵中查找得出。由于该程序中使用的是前向矩阵，因此在查找的过程中，路由矩阵中 r(i,j)对应的值为 Vi 到
5、Vj 路由上的下一个端点，这样再代入 r(r(i,j),j)，可得到下下个端点，由此不断循环下去，即可找到最终的路由。（3）对图 1，分别以端点对 V4 和 V6, V3 和 V4 为例，求其最短距离和路由；对图 2，分别以端点对 V1 和 V7，V3 和 V5，V1 和 V6 为例，求其最短距离和路由。3、输入一邻接权值矩阵，求解最短距离和路由矩阵，及某些点间的最短路径。4、扩展的实验内容（选作部分）（1）实现 Floyd 算法的回溯路由矩阵；（2）探讨可降低算法复杂度的算法。通信网理论基础实验报告第 3 页 四、程序基本信息1、设计语言及开发工具：、设计语言及开发工具： MATLAB。 2
6、、数据结构：、数据结构： 本次实验涉及到了数据结构中图的相关内容，如图的遍历等等。另外，实 验中采用不定长数组存储算法的相关矩阵信息。 3、主要函数（算法）：、主要函数（算法）： 本程序采用 MATLAB 语言编写，程序文件名为 Floyd.m。 第一部分：Floyd 算法求出其各个端点之间的最小距离以及路由 这里包含两种路由方法的 Floyd 算法：前向路由和回溯路由。下面先介绍 其中的前向路由方法部分。它的主要思想及流程在实验原理部分已给出，下页 以流程图的形式给出该段程序的工作流程，和原算法本身相比并无太多不同。 回溯路由方法的 Floyd 算法流程如下：F0：初始化距离矩阵和路由矩阵。
7、其中：(0)W(0)R(0)0ijijijijweEweEij 若（有边）若（无边）若(对角线元素)(0) (0)w 0,ij ijir 若其它F1：已求得和，依据下面的迭代求和( -1)kW( -1)kR( )kW( )kR( )(1)(1)( -1) ,min(,)kkkk i ji ji kk jwwww(1)( )(1) ,( ) ,(1)( )(1) ,kkk k ji ji jk i jkkk i ji ji jrwwrrww若若F2：若，重复 F1；若，终止。knkn可见该算法仅在路由矩阵更新方面有些许不同，因此这里不再给出它的流 程图。 另外要说明的一点是，程序中无法表示，用
8、100 代替。通信网理论基础实验报告第 4 页 Floyd 算法（前向路由）流程图开始获取输入的距 离矩阵阶数n输入的矩阵作 为距离矩阵W0构造n阶全0矩 阵R0，用于存 储路由信息初始化矩阵R0，若 W0中位置(I,j)的元 素不为100，则R0 中对应位置元素置 为j，否则为0置k=1产生矩阵Wk，方法： Wk(i,j)取Wk-1(I,j)和Wk- 1(i,k)+Wk-1(k,j)的较小值产生矩阵Rk，方法： 若Wk(I,j)n?输出矩阵Wk和Rk结束通信网理论基础实验报告第 5 页 第二部分：Floyd 算法程序改进 Floyd 算法中，距离矩阵每次更新的元素非常少（相对于矩阵元素总个数
9、而 言），而路由矩阵又随着距离矩阵的更新而更新。原先的程序中无论是否更新 都要执行一次赋值操作，其实只需要保留需要更新值的赋值操作，不更新值的 赋值操作没有意义。因此优化后的程序可以大大减少赋值次数。这个程序其实 没有改变原算法思想，只是针对程序本身进行了优化。 第三部分：查询任意两点间的最短距离和路由 这段算法非常简单，主要利用了 Floyd 算法生成的距离矩阵和路由矩阵， 以下简述它的工作流程：开始输入源端点i 和目的端点j返回距离矩 阵位置为(i,j) 的元素值即 最短距离查询路由矩阵 中位置为（i,j) 的元素值元素值为j？记录查询到的 值，并将其赋给i否按顺序返 回以上查 询到的值结
10、束是通信网理论基础实验报告第 6 页 五、程序运行结果与分析1、利用给定的两个路由矩阵判定算法正确性：、利用给定的两个路由矩阵判定算法正确性：/(0)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.5 1.2 5 100 0 6.7 100 100 9.2 100 100 6.7 0 15.6 100 100 3.1 4 100 15.6 0 100 0.5 2 1.5 100 100 100 0W (0)0 0.5 2 1.5 100 100 1000.5 0 100 100 1.2 9.2 100
11、2 100 0 100 5 100 3.1 1.5 100 100 0 100 100 4100 1.2 5 100 0 6.7 100 100 9.2 100 100 6.7 0 15.6 100 100 3.1 4 100 15.6 0W 矩阵 1 的执行结果：通信网理论基础实验报告第 7 页 矩阵 2 的执行结果：注：上面的运行结果中，W1 为最短距离矩阵，R1 为最短路由（前向）矩 阵，R2 为最短路由（回溯）矩阵。 2、根据最短路由矩阵查询任意两点间的最短距离和路由：、根据最短路由矩阵查询任意两点间的最短距离和路由： 以下查询均使用前向最短路由矩阵。 矩阵 1：V4 到 V6，V3
12、到 V4。通信网理论基础实验报告第 8 页 即 V4 到 V6 的最短距离：6.8，最短路由：V4V1V7V2V6； V3 到 V4 的最短距离：3.2，最短路由：V3V7V1V4。矩阵 2：V1 到 V7，V3 到 V5，V1 到 V6。即 V1 到 V7 的最短距离：5.1，最短路由：V1V3V7； V3 到 V5 的最短距离：3.7，最短路由：V3V1V2V5； V1 到 V6 的最短距离：8.4，最短路由：V1V2V5V6。 3、原程序与改进后的程序运行结果及时间比较：、原程序与改进后的程序运行结果及时间比较： 采用矩阵 1 进行测试。 测试时，原程序的回溯矩阵处理语句被注释掉，即不让
13、它处理回溯矩阵， 同时两个程序的初始化矩阵 W0和 R0的时间都不考虑。 原程序运行结果：通信网理论基础实验报告第 9 页 改进后程序运行结果：通信网理论基础实验报告第 10 页 这里仅给出一次运行的结果。由上图可见，两个算法的运行结果是完全相 同的（路由矩阵对角线上的元素不同，但是实际应用时对角线上的元素值没有 意义），且优化后的程序执行时间比未优化的程序短。当然，每次运行结果都 是不同的，有极小的可能会出现二者执行时间近似甚至优化后程序超过未优化 程序。由于时间所限，无法对每次的运行时间加以统计，但大致上，优化后程 序平均起来运行时间要比未优化的程序短 20%到 30%。对于阶数较大的输入
14、矩 阵，优化后程序的性能提升更为明显。六、遇到的主要问题1、Wk和和 Rk矩阵的表示问题矩阵的表示问题两个矩阵本身是二维的，又要考虑一个 k 变量，因此采用三维数组。另外 由于 W 和 R 矩阵都有一个初始矩阵 W0和 R0，因此 k 取值范围为 1 到 n+1（n 为方阵阶数）。2、多次执行查询两点间最短距离和路由算法时，输出的最短路由出现错误。、多次执行查询两点间最短距离和路由算法时，输出的最短路由出现错误。该问题当上一次执行的路由比这次的多时就会出现。每次执行都要处理一 个数组并输出它的所有内容，出现错误的原因是本次算法执行前数组没有清空， 导致前一次的路由信息也一并输出了。七、实验总结
