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

《北邮信息工程通信网理论基础实验4报告——floyd算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、离矩阵和路由矩阵。其中：F1：已求得和，依据下面的迭代求和F2：若，重复F1；若，终止。第10页通信网理论基础实验报告二、实验内容用MATLAB仿真工具实现Floyd算法：给定图及其边的权，求出其各个端点之间的最小距离以及路由。1、分别用以下两个初始距离矩阵表示的图进行算法验证：分别求出和。2、根据最短路由矩阵查询任意两点间的最短距离和路由（1）最短距离可以从最短距离矩阵的中直接得出；（2）相应的路由则可以通过在路由矩阵中查找得出。由于该程序中使用的是前向矩阵，因此在查找的过程中，路由矩阵中r(i,j)对应的值为Vi到Vj路由上的下一个端点

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

4、的相关内容，如图的遍历等等。另外，实验中采用不定长数组存储算法的相关矩阵信息。3、主要函数（算法）：本程序采用MATLAB语言编写，程序文件名为Floyd.m。第一部分：Floyd算法求出其各个端点之间的最小距离以及路由这里包含两种路由方法的Floyd算法：前向路由和回溯路由。下面先介绍其中的前向路由方法部分。它的主要思想及流程在实验原理部分已给出，下页以流程图的形式给出该段程序的工作流程，和原算法本身相比并无太多不同。回溯路由方法的Floyd算法流程如下：F0：初始化距离矩阵和路由矩阵。其中：F1：已求得和，依据下面的迭代求和F2：若，重

5、复F1；若，终止。可见该算法仅在路由矩阵更新方面有些许不同，因此这里不再给出它的流程图。另外要说明的一点是，程序中无法表示，用100代替。第10页通信网理论基础实验报告Floyd算法（前向路由）流程图第10页通信网理论基础实验报告第二部分：Floyd算法程序改进Floyd算法中，距离矩阵每次更新的元素非常少（相对于矩阵元素总个数而言），而路由矩阵又随着距离矩阵的更新而更新。原先的程序中无论是否更新都要执行一次赋值操作，其实只需要保留需要更新值的赋值操作，不更新值的赋值操作没有意义。因此优化后的程序可以大大减少赋值次数。这个程序其实没有改变原

6、算法思想，只是针对程序本身进行了优化。第三部分：查询任意两点间的最短距离和路由这段算法非常简单，主要利用了Floyd算法生成的距离矩阵和路由矩阵，以下简述它的工作流程：第10页通信网理论基础实验报告五、程序运行结果与分析1、利用给定的两个路由矩阵判定算法正确性：矩阵1的执行结果：第10页通信网理论基础实验报告矩阵2的执行结果：注：上面的运行结果中，W1为最短距离矩阵，R1为最短路由（前向）矩阵，R2为最短路由（回溯）矩阵。2、根据最短路由矩阵查询任意两点间的最短距离和路由：以下查询均使用前向最短路由矩阵。矩阵1：V4到V6，V3到V4。第1

7、0页通信网理论基础实验报告即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进行测试。测试时，原程序的回溯矩阵处理语句被注释掉，即不让它处理回溯矩阵，同时两个程序的初始化矩阵

8、W0和R0的时间都不考虑。原程序运行结果：第10页通信网理论基础实验报告改进后程序运行结果：第10页通信网理论基础实验报告这里仅给出一次运行的结果。由上图可见，两个算法的运行结果