资源描述：
《利用MATLAB实现Dijkstra算法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、利用计算机语言编程实现D算法一：实验目的本实验课程主要目的是让学生够熟练掌握图论中的D算法。二：实验方法选择MATLAB语言编程实现D算法。三：实验要求1.输入必要参数，包括：节点个数、节点间路径长度、给定节点；2.输出给定节点到其它各节点的最短路径、径长；3.节点间路径长度用矩阵形式表示。四：实验内容无向图共有7个节点，如下图所示。计算机输入的节点间路径长度为7×7矩阵：若为指定节点，则到其它各节点的最短路径及径长的计算机计算结果为：节点最短路径径长01237614提示：不相邻的两个节点间可以用相对较大的数代替（如输入
2、100表示）五：实验原理1.D算法原理已知图G=(V,E)，将其节点集分为两组：置定节点集和未置定节点集。其中内的所有置定节点，是指定点到这些节点的路径为最短（即已完成最短路径的计算）的节点。而内的节点是未置定节点，即到未置定节点距离是暂时的，随着算法的下一步将进行不断调整，使其成为最短径。在调整各未置定节点的最短径时，是将中的节点作为转接点。具体地说，就是将中的节点作为转接点，计算（,）的径长（），若该次计算的径长小于上次的值，则更新径长，否则，径长不变。计算后取其中径长最短者，之后将划归到中。当（）最终成为空集，同时
3、，即求得到所有其他节点的最短路径。表示与其他节点的距离。在中，表示上一次划分到中的节点到得最短路径。在中，表示到（）仅经过中的节点作为转接点所求得的该次的最短路径的长度。如果与不直接相连，且无置定节点作为转接点，则令=。2.D算法实现流程D算法流程如下图所示。六：例题的计算过程表1D算法计算过程迭代次数置定节点Gp0=01=12=23=34=65=76=14表2到其他各节点的最短路径和径长节点最短路径径长01236714七:仿真过程1.输入参数：a.输入无向图的节点个数提示：‘Pleaseinputnumberofthe
4、notes:k=’输入：7；b.输入对应节点个数的k×k大小的矩阵，并且具有检测能力，如果矩阵大小不匹配，提示重新输入提示：‘Note:Ifthereisnodirectlinkbetweennotes,use100toreprsentinfinitePleaseinputthek*kmatrixofthelengthofpath:M=’输入：[0,1,2,3,100,100,100;1,0,100,100,100,6,100;2,100,0,100,5,4,100;3,100,100,0,4,100,100;100,1
5、00,5,4,0,100,7;100,6,4,100,100,0,8;100,100,100,100,7,8,0]若输入错误，提示：‘pleaseinputthecorrectsizeofthematrix，Pleaseinputthek*kmatrixofthelengthofpath:M=’c.输入起始节点提示：‘Pleaseidentifytheinitialnote:s’输入：1。2.输出结果a.输出最短路径矩阵（起始节点为）s=1111111023433300006560000007c.输出对应的路径长度（与s
6、顺序对应）d=012367141.运行结果截屏
