当前位置:文档之家› 利用计算机语言编程实现D算法

利用计算机语言编程实现D算法

Harbin Institute of Technology
通信网理论与技术报告
题目:利用计算机语言编程实现D算法
院(系)电子与信息工程学院
班级通信1班
学生
学号
哈尔滨工业大学
利用计算机语言编程实现D算法
1 D算法简介
Dijkstra(狄克斯特拉)算法用于计算通信网中指定节点到其他各节点的最短路径,简称D算法。

本实验课程主要目的利用计算机语言编程实现D算法。

D算法是通过对路径的长度进行迭代,从而计算出到达目的节点的最短路径。

其基本思想为:按照路径长度增加的顺序来寻找最短路径。

步骤:假定节点begin为源节点,则
(1)初始化:置N={begin},对不属于N的结点v,置D(v)=w(begin,v)。

(2)迭代:
①寻找下一个与节点begin最近的节点u,加入到N中。

如果N中包括了所有的节点,则算法结束。

②对所有不属于N的结点v按下式更新
D(v):D(v)=min[D(v),D(u)+weight(u,v)]
2编程环境及输入输出参数
本实验使用Matlab软件,Matlab具有强大的数据处理能力和完备的图形处理功能。

学生利用Matlab编写了D算法的函数,函数名为dijkstra.m。

本函数包含3个输入参数:结点个数n,节点间路径长度矩阵weight,给定节点begin;两个输出参数:给定节点到其它各节点的最短路径矩阵path_matrix、径长min。

3例题的运算结果
本实验中的例题为:
无向图共有7 个节点,如下图所示。

图1 7节点无向图
若v1为指定节点,计算机编程实现v1到其它各节点的最短路径及径长。

文件dijkstra_test1.m即为利用D算法实现上述要求的源程序,程序调用D 算法函数dijkstra.m。

输入的权值矩阵如图2。

节点1到各节点的最短路径矩阵形式输出如图3,该矩阵中第i行即表示节点1到节点i的路径,矩阵中的0没有意义,可略去不看。

节点1到各节点的最短路径径长如图4所示,其中第j列表示节点1到节点j的最短路径径长。

需要注意的是,图3中给出的节点1到节点5路径(1,3,5)与老师给的文档中路径(1,4,5)不相同,这是因为他们的路径径长均为7,都是最短路径,按照学生的编程顺序,程序选择了(1,3,5),节点1到节点7路径也是类似的情况。

图2 输入的权值矩阵
图3节点1到各节点的最短路径
图4节点1到各节点的最短路径径长
图5,图6和图7给出了程序运行之后在命令窗的输出(分三次截图)。

图5 命令窗口输出
图6命令窗口输出
图7命令窗口输出4 例题的计算过程
本题的计算过程可用表1来表示。

表1 例题计算过程
5随机产生不完全连通图验证D算法
为了更好的验证编写的D算法程序的确定性,学生结合本科时候做过的实验,编写了输入节点数量,随机产生网孔型(不完全网状网)网络拓扑的函数net_produce.m,其中相互连接的节点间路径长度为1-10之间的整数。

文件dijkstra_test2为节点数为6,先随机产生一张不完全网状网,然后计算节点1到各节点的最短路径及相应径长的源程序。

运行文件dijkstra_test2后,随机生成的权值矩阵如图8,对应的网络拓扑如图9,节点1到各节点的最短路径矩阵如图10,与前面介绍的相同,该矩阵中第i行即表示节点1到节点i的路径,矩阵中的0没有意义,可略去不看。

节点1到各节点的最短路径径长如图11所示,其中第j列表示节点1到节点j的最短路径径长。

图8随机生成的权值矩阵
图9对应的网络拓扑
图10节点1到各节点的最短路径
图11节点1到各节点的最短路径径长
5 小结
本实验完成了所有的实验要求,并经行了发挥,本次实验学生收获很大,对于图论的基本知识有了很深的理解,同时也很好的掌握了D算法,再一次练习了Matlab编程。

另外,在学生编程实现随机生成不完全网状网的过程中遇到了很多问题,但是最后都得到了圆满的解决,在一过程中,学生接触并理解掌握了图论的基本知识,收益很深。

相关主题