实验三—最短路径算法

《通信网理论基础》

实 验 指 导 书

适用专业—信息工程

实验三：端间最短路径算法的仿真实现

一、实验目的

通信网络中为传输信息，需要求解网络中端点之间的最短距离和路由。此时网络可以用图G＝（V,E)来表示，每条边(i,j)的权wi,j可为该边的距离、成本或容量等物理意义。端间最短径问题主要分为两种情况：寻找指定端至任意其它端之间的最短距离和路由，可以使用Dijkstra算法解决；寻找任意两端之间的最短距离和路由, 使用Floyd算法解决。

Dijkstra算法为标号置定法，通过依次置定指定端与当前端的最短距离和回溯路由来实现；Floyd算法为标号修正法，通过初始化图的距离矩阵和路由矩阵、并在迭代过程中不断刷新最短距离和路由信息，直至算法结束才能求出任意两点间的最短距离矩阵和前向（或反向）路由矩阵。

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

二、实验原理

2.1 Dijkstra算法描述如下：

D算法的每个端点vi的标号为(?i,l)，其中?i表示v1到vi的距离，而l为端点是v1到vi最短路径的最后一个端点。

（V，E）图G?的每一边上有一个权w(e)?0。

D0：初始X(0)?{v1}，记?1?0，设v1的标号为(?1,1)。

D1：对任一边(i,l)?反圈?(X(k))(vi?X(k),vl?X(k))，计算?i?wil的值。在?(X(k))中选一边，设为(i0,l0)(vi0?X(k),vl0?X(k))。使?i0?wi0l0?。 ?l??i?wil，并且vl的标号为（?l,i0）000000(i,l)??(X(k))min(?i?wil)，并令

D2：当出现下面情况之一时停止。

)1）vj?X(k)；2）vj?X(k)但?(X(k）??

2.2 Floyd算法可描述如下：

给定图G及其边(i,j)的权wi,j(1?i?n,1?j?n) F0：初始化距离矩阵W(0)和路由矩阵R(0)。其中：

?wij　若eij?E????　若eij?E ?0　　若i?j?wij(0)rij(0)?j　若wij(0)?? ??　　其它?0,F1：对于已求得的W(k-1)和R(k-1)，依据下面的迭代求解W(k)和R(k)。

?1)(k-1)wi(,kj)?min(wi(,kj?1),wi(,k?wkk,j)

ri,j(k)(k?1)(k)(k?1)??ri,k　若wi,j?wi,j??(k?1) (k)(k?1)r　若w?w?i,ji,j?i,jF2：若k?n，重复F1；若k?n，终止。

三、实验内容

用MATLAB仿真工具实现D算法和F算法：给定图G及其边(i,j)的权

wi,j(1?i?n,1?j?n)，可用D算法和F算法分别求出其各个端点之间的最小距离以及路由。

1、分别用以下两个初始距离矩阵表示的图进行算法验证：

图1 W(0)?0 100 100 1.2 9.2 100 0.5??0 0.5 2 1.5 100 100 100??100 0 100 5 100 3.1 2??0.5 0 100 100 1.2 9.2 100??????100 100 0 100 100 4 1.5??2 100 0 100 5 100 3.1???????1.2 5 100 0 6.7 100 100? 图2 W(0)??1.5 100 100 0 100 100 4? ?9.2 100 100 6.7 0 15.6 100??100 1.2 5 100 0 6.7 100?????100 3.1 4 100 15.6 0 100100 9.2 100 100 6.7 0 15.6?????0.5 2 1.5 100 100 100 0]??100 100 3.1 4 100 15.6 0?????分别利用D算法和F算法求出W(7)和R(7)。

2、根据最短路由矩阵查询任意两点间的最短距离和路由

（1）最短距离可以从最短距离矩阵中直接得出。

（2）相应的路由则可以通过在路由矩阵中查找得出。注意D算法应用回溯路由，F算法可应用回溯路由或正向路由。

（3）对图1，分别以端点对V4和V6, V3和V4为例，求其最短距离和路由；对图2，分别以端点对V1和V7，V3和V5，V1和V6为例，求其最短距离和路由。

3、输入任一邻接权值矩阵，求解最短距离和路由矩阵，及某些点间的最短路径。 4、扩展的实验内容（选作部分）

（1）比较D算法和F算法在功能和算法复杂度上的性能； （2）探讨可降低算法复杂度的算法。

四、实验难点

(1) 图的等价表示方法； (2) 两点间的最短路径查询算法。

五、实验报告

请提交电子版实验报告，内容包括但不限于以下方面： 实验内容；

? 所采取的实验方法：采用的语言，数据结构，主要的函数，算法的流程

图等；

? 实验数据与结论分析；

? 遇到的问题及解决方法：对算法或编程方面遇到的问题，查阅相关资料

或搜索电子资源，描述出现问题的原因以及解决的方案。 ? 其他的有价值和意义的内容。 五、注意事项

? Deadline：2016年6月8号下午5点前。

? 请将两个算法的源代码文件分别打包，然后加上实验报告后再次打包，以“班

级_姓名1_姓名2.rar”发送1297908068@qq.com和18817393031@163.com。 ? 杜绝抄袭，一旦发现，以

0分论处。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库实验三—最短路径算法在线全文阅读。