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

信息与通信工程学院 通信网理论基础实验报告

班 级： 姓 名： 学 号： 序 号： 通信网理论基础实验报告

第1页 实验四 Floyd算法

一、实验目的 Floyd算法通过图的权值矩阵求出任意两点间的最短距离矩阵和路由矩阵。优点是容易理解，可以算出任意两个节点之间最短距离的算法，且程序容易实现，缺点是复杂度达到 ，不适合计算大量数据。

本次实验要求利用MATLAB实现Floyd算法，可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。

二、 实验原理 Floyd算法可描述如下： 给定图G及其边(,)ij的权,(1,1)ijwinjn F0：初始化距离矩阵(0)W和路由矩阵(0)R。其中：

(0)0ijijijijweEweEij　若（有边）　若（无边） 若(对角线元素)

(0)(0)w0,ijijjr　若

其它

F1：已求得(-1)kW和(-1)kR，依据下面的迭代求()kW和()kR

()(1)(1)(-1),,,,min(,)kkkkijijikkjwwww

(1)()(1),,,(),(1)()(1),,,kkkikijijkijkkkijijijrwwrrww

　若

　若

F2：若kn，重复F1；若kn，终止。 通信网理论基础实验报告 第2页 三、 实验内容 用MATLAB仿真工具实现Floyd算法：给定图G及其边(,)ij的权,(1,1)ijwinjn，求出其各个端点之间的最小距离以及路由。 1、分别用以下两个初始距离矩阵表示的图进行算法验证：

(0)0 100 100 1.2 9.2 100 0.5100 0 100 5 100 3.1 2100 100 0 100 100 4 1.51.2 5 100 0 6.7 100 1009.2 100 100 6.7 0 15.6 100100 3.1 4 100 15.6 0 1000.5 2 1.5 100 100 100 0]W



(0)0 0.5 2 1.5 100 100 1000.5 0 100 100 1.2 9.2 1002 100 0 100 5 100 3.11.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 0W



分别求出(7)W和(7)R。 2、根据最短路由矩阵查询任意两点间的最短距离和路由 （1）最短距离可以从最短距离矩阵的ji,中直接得出； （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、输入一邻接权值矩阵，求解最短距离和路由矩阵，及某些点间的最短路径。 4、扩展的实验内容（选作部分） （1）实现Floyd算法的回溯路由矩阵； （2）探讨可降低算法复杂度的算法。 通信网理论基础实验报告 第3页 四、程序基本信息 1、设计语言及开发工具： MATLAB。 2、数据结构： 本次实验涉及到了数据结构中图的相关内容，如图的遍历等等。另外，实验中采用不定长数组存储算法的相关矩阵信息。 3、主要函数（算法）： 本程序采用MATLAB语言编写，程序文件名为Floyd.m。 第一部分：Floyd算法求出其各个端点之间的最小距离以及路由 这里包含两种路由方法的Floyd算法：前向路由和回溯路由。下面先介绍其中的前向路由方法部分。它的主要思想及流程在实验原理部分已给出，下页以流程图的形式给出该段程序的工作流程，和原算法本身相比并无太多不同。 回溯路由方法的Floyd算法流程如下：

F0：初始化距离矩阵(0)W和路由矩阵(0)R。其中：

(0)0ijijijijweEweEij　若（有边）　若（无边） 若(对角线元素)

(0)(0)w0,ijijir　若

其它

F1：已求得(-1)kW和(-1)kR，依据下面的迭代求()kW和()kR

()(1)(1)(-1),,,,min(,)kkkkijijikkjwwww

(1)()(1),,,(),(1)()(1),,,kkkkjijijkijkkkijijijrwwrrww

　若

　若

F2：若kn，重复F1；若kn，终止。 可见该算法仅在路由矩阵更新方面有些许不同，因此这里不再给出它的流程图。 另外要说明的一点是，程序中无法表示，用100代替。 通信网理论基础实验报告 第4页 开始

获取输入的距离矩阵阶数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)Rk(I,j)=Rk-1(I,k)，否则Rk(I,j)=Rk-1(I,j)

k=k+1

k>n?输出矩阵Wk和Rk结束Floyd算法（前向路由）流程图 通信网理论基础实验报告 第5页 第二部分：Floyd算法程序改进 Floyd算法中，距离矩阵每次更新的元素非常少（相对于矩阵元素总个数而言），而路由矩阵又随着距离矩阵的更新而更新。原先的程序中无论是否更新都要执行一次赋值操作，其实只需要保留需要更新值的赋值操作，不更新值的赋值操作没有意义。因此优化后的程序可以大大减少赋值次数。这个程序其实没有改变原算法思想，只是针对程序本身进行了优化。 第三部分：查询任意两点间的最短距离和路由 这段算法非常简单，主要利用了Floyd算法生成的距离矩阵和路由矩阵，以下简述它的工作流程：

开始

输入源端点i和目的端点j

返回距离矩阵位置为(i,j)的元素值即最短距离

查询路由矩阵中位置为（i,j)的元素值

元素值为j？记录查询到的值，并将其赋给i

否

按顺序返回以上查询到的值

结束

是 通信网理论基础实验报告

第6页 五、程序运行结果与分析 1、利用给定的两个路由矩阵判定算法正确性：

(0)0 100 100 1.2 9.2 100 0.5100 0 100 5 100 3.1 2100 100 0 100 100 4 1.51.2 5 100 0 6.7 100 1009.2 100 100 6.7 0 15.6 100100 3.1 4 100 15.6 0 1000.5 2 1.5 100 100 100 0]W



(0)0 0.5 2 1.5 100 100 1000.5 0 100 100 1.2 9.2 1002 100 0 100 5 100 3.11.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 0W



矩阵1的执行结果： 通信网理论基础实验报告

第7页 矩阵2的执行结果：

注：上面的运行结果中，W1为最短距离矩阵，R1为最短路由（前向）矩阵，R2为最短路由（回溯）矩阵。 2、根据最短路由矩阵查询任意两点间的最短距离和路由： 以下查询均使用前向最短路由矩阵。 矩阵1：V4到V6，V3到V4。 通信网理论基础实验报告

第8页 即V4到V6的最短距离：6.8，最短路由：V4→V1→V7→V2→V6； V3到V4的最短距离：3.2，最短路由：V3→V7→V1→V4。

矩阵2：V1到V7，V3到V5，V1到V6。

即V1到V7的最短距离：5.1，最短路由：V1→V3→V7； V3到V5的最短距离：3.7，最短路由：V3→V1→V2→V5； V1到V6的最短距离：8.4，最短路由：V1→V2→V5→V6。 3、原程序与改进后的程序运行结果及时间比较： 采用矩阵1进行测试。 测试时，原程序的回溯矩阵处理语句被注释掉，即不让它处理回溯矩阵，同时两个程序的初始化矩阵W0和R0的时间都不考虑。 原程序运行结果：