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编程。

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