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

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

2、中：F0：初始化距离矩阵(0)(0)RW（有边）E若e?w?ijij?(0)（无边）E若e?w? ?ijij?)对角线元素?j(0若i?(0)?w?j若(0)ij?r ?ij其它0,?)k()k(WR-1)k(-1)(k和和，依据下面的迭代求F1：已求得RW k(?1)(?1)(k-1)k)k )ww,w?w?min(j,jki,jkii,1)?(k?1)(k)(k?ww?r若?jjii,k,i )(k?r?j,i1)?(k)(k?1)(kww?若r?jj,i,jii, ，终止。；若，重复F2：若F1nk?kn? 1第页 通信网理论基础实验报告 实验内容三、)j(i,G权边的及其法MATLAB

3、仿真工具实现Floyd算：给定图用，求出其各个端点之间的最小距离以及路由。 )j?n?n,1?w(1?ij,i 、分别用以下两个初始距离矩阵表示的图进行算法验证：10 0.5 2 1.5 100 100 100?0 100 100 1.2 9.2 100 0.5?0.5 0 100 100 1.2 9.2 100100 0 100 5 100 3.1 2?2 100 0 100 5 100 3.1?100 100 0 100 100 4 1.5 ?(0)(0)1.5 100 100 0 100 100 4?WW?1.2 5 100 0 6.7 100 100?100 1.2 5 100 0 6

4、.7 1009.2 100 100 6.7 0 15.6 100?100 9.2 100 100 6.7 0 15.6100 3.1 4 100 15.6 0 100?100 100 3.1 4 100 15.6 00.5 2 1.5 100 100 100 0?(7)R(7) 和。分别求出W 、根据最短路由矩阵查询任意两点间的最短距离和路由2?ji, ）最短距离可以从最短距离矩阵的中直接得出；（1相应的路由则可以通过在路由矩阵中查找得出。由于该程序中使用 2）（路到Vj的是前向矩阵，因此在查找的过程中，路由矩阵中r(i,j)对应的值为Vi，可得到下下个端点，由此不断循环下由上的下一个端点，这

5、样再代入r(r(i,j),j) 去，即可找到最终的路由。为例，求其最短距离和路V4V6, V3和1（3）对图，分别以端点对V4和为例，求其最短距和V6和V5，V1V3V1由；对图2，分别以端点对和V7， 离和路由。 、输入一邻接权值矩阵，求解最短距离和路由矩阵，及某些点间的最短路径。3 、扩展的实验内容（选作部分）4 Floyd算法的回溯路由矩阵；（1）实现 ）探讨可降低算法复杂度的算法。（2 2第页 通信网理论基础实验报告 四、程序基本信息 1、设计语言及开发工具： MATLAB。 2、数据结构：本次实验涉及到了数据结构中图的相关内容，如图的遍历等等。另外，实 验中采用不定长数组存储算法的相

6、关矩阵信息。 3、主要函数（算法）： Floyd.m。本程序采用MATLAB语言编写，程序文件名为 Floyd算法求出其各个端点之间的最小距离以及路由第一部分：算法：前向路由和回溯路由。下面先介绍这里包含两种路由方法的Floyd其中的前向路由方法部分。它的主要思想及流程在实验原理部分已给出，下页 以流程图的形式给出该段程序的工作流程，和原算法本身相比并无太多不同。 Floyd算法流程如下：回溯路由方法的 和路由矩阵。其中：F0：初始化距离矩阵(0)(0)RW（有边）?Ew若e?ijij?(0)（无边）wE若e? ?ijij?)对角线元素?j(0若i?(0)?若w?i(0)ij?r ?ij其它0

7、,?)(k)(kWR-1)k(-1)k(和：已求得，依据下面的迭代求和F1RW kk(?1)()k?1)(-1)(k )w?w?min(w,wjki,jii,j,k1)?)(kk?1)(k(?w?若wr?jii,kjj, )k(?r?ji,1)k?k)(k(?1)(w?r若w?j,i,jii,j ，终止。F1F2：若，重复；若nk?nk?可见该算法仅在路由矩阵更新方面有些许不同，因此这里不再给出它的流 程图。? 代替。另外要说明的一点是，程序中无法表示，用100 3第页 通信网理论基础实验报告 开获取输入的离矩阵阶输入的矩阵为距离矩构阶，用于储路由信，初始化矩的(I,j中位素不10，中对应位置

8、元素，否则k=，方法产生矩kk-(I,j(i,jk-的较小(i,k)+(k,j，方法产生矩k-，(I,j)n输出矩结束 Floyd算法（前向路由）流程图 第4页 通信网理论基础实验报告 Floyd算法程序改进第二部分：算法中，距离矩阵每次更新的元素非常少（相对于矩阵元素总个数而Floyd言），而路由矩阵又随着距离矩阵的更新而更新。原先的程序中无论是否更新都要执行一次赋值操作，其实只需要保留需要更新值的赋值操作，不更新值的赋值操作没有意义。因此优化后的程序可以大大减少赋值次数。这个程序其实 没有改变原算法思想，只是针对程序本身进行了优化。 第三部分：查询任意两点间的最短距离和路由算法生成的距离矩

9、阵和路由矩阵，Floyd这段算法非常简单，主要利用了 以下简述它的工作流程： 开输入源端和目的端返回距离(i,j阵位置的元素值最短距查询路由矩i,j中位置为的元素元素值否记录查询到的i值，并将其赋给按顺序返回以上查询到的值结束 5第页 通信网理论基础实验报告 五、程序运行结果与分析 、利用给定的两个路由矩阵判定算法正确性：10 0.5 2 1.5 100 100 100?0 100 100 1.2 9.2 100 0.5?0.5 0 100 100 1.2 9.2 100100 0 100 5 100 3.1 2?2 100 0 100 5 100 3.1?100 100 0 100 100

10、4 1.5 ?(0)(0)1.5 100 100 0 100 100 4W?1.2 5 100 0 6.7 100 100W?100 1.2 5 100 0 6.7 1009.2 100 100 6.7 0 15.6 100?100 9.2 100 100 6.7 0 15.6100 3.1 4 100 15.6 0 100?100 100 3.1 4 100 15.6 00.5 2 1.5 100 100 100 0? 的执行结果：矩阵1 第6页 通信网理论基础实验报告 矩阵2的执行结果： 为最短路由（前向）矩为最短距离矩阵，R1注：上面的运行结果中，W1 R2为最短路由（回溯）矩阵。阵，

11、、根据最短路由矩阵查询任意两点间的最短距离和路由：2 以下查询均使用前向最短路由矩阵。 V4到。V3V6V41矩阵：到， 7第页 通信网理论基础实验报告 ；6.8，最短路由：V4V1V7V2V6即V4到V6的最短距离： ，最短路由：V3V7V1V4。V3到V4的最短距离：3.2 V6。到V5，V1到，矩阵2：V1到V7V3 ；V3V7的最短距离：即V1到V75.1，最短路由：V1 V5；V33.7，最短路由：V1V2V5V3到的最短距离： 。V5V6的最短距离：V1到V68.4，最短路由：V1V2 3、原程序与改进后的程序运行结果及时间比较： 采用矩阵1进行测试。测试时，原程序的回溯矩阵处理语

12、句被注释掉，即不让它处理回溯矩阵，00 和R的时间都不考虑。同时两个程序的初始化矩阵W 原程序运行结果： 第8页 通信网理论基础实验报告 改进后程序运行结果： 9第页 通信网理论基础实验报告 这里仅给出一次运行的结果。由上图可见，两个算法的运行结果是完全相 同的（路由矩阵对角线上的元素不同，但是实际应用时对角线上的元素值没有意义），且优化后的程序执行时间比未优化的程序短。当然，每次运行结果都是不同的，有极小的可能会出现二者执行时间近似甚至优化后程序超过未优化程序。由于时间所限，无法对每次的运行时间加以统计，但大致上，优化后程。对于阶数较大的输入矩到30%序平均起来运行时间要比未优化的程序短20% 阵，优化后程序的性能提升更为明显。 六、遇到的主要问题kk 和R矩阵的表示问题1、W变量，因此采用三维数组。另外k两个