利用MATLAB实现Dijkstra算法

利用计算机语言编程实现D算法一：实验目的本实验课程主要目的是让学生够熟练掌握图论中的D算法。二：实验方法选择MATLAB语言编程实现D算法。三：实验要求1. 输入必要参数，包括：节点个数、节点间路径长度、给定节点；2. 输出给定节点到其它各节点的最短路径、径长；3. 节点间路径长度用矩阵形式表示。四：实验内容无向图共有7个节点，如下图所示。计算机输入的节点间路径长度为77矩阵：若为指定节点，则到其它各节点的最短路径及径长的计算机计算结果为：节点最短路径径长01237614提示：不相邻的两个节点间可以用相对较大的数代替（如输入100表示）五：实验原理1. D算法原理已知图G=(V,E)，将其节点集分为两组：置定节点集和未置定节点集。其中内的所有置定节点，是指定点到这些节点的路径为最短（即已完成最短路径的计算）的节点。而内的节点是未置定节点，即到未置定节点距离是暂时的，随着算法的下一步将进行不断调整，使其成为最短径。在调整各未置定节点的最短径时，是将中的节点作为转接点。具体地说，就是将中的节点作为转接点，计算（,）的径长（），若该次计算的径长小于上次的值，则更新径长，否则，径长不变。计算后取其中径长最短者，之后将划归到中。当（）最终成为空集，同时，即求得到所有其他节点的最短路径。表示与其他节点的距离。在中，表示上一次划分到中的节点到得最短路径。在 中，表示到（）仅经过中的节点作为转接点所求得的该次的最短路径的长度。如果与不直接相连，且无置定节点作为转接点，则令=。2. D算法实现流程D算法流程如下图所示。六：例题的计算过程表1 D算法计算过程迭代次数置定节点Gp0=01=12=23=34=65=76=14表2 到其他各节点的最短路径和径长节点最短路径径长01236714七:仿真过程1. 输入参数：a. 输入无向图的节点个数提示：Please input number of the notes: k=输入：7；b. 输入对应节点个数的kk大小的矩阵，并且具有检测能力，如果矩阵大小不匹配，提示重新输入提示：Note: If there is no direct link between notes, use 100 to reprsent infinitePlease input the k*k matrix of the length of path: 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,100,5,4,0,100,7;100,6,4,100,100,0,8;100,100,100,100,7,8,0若输入错误，提示：please input the correct size of the matrix，Please input the k*k matrix of the length of path: M=c. 输入起始节点提示：Please identify the initial note: s输入：1。2. 输出结果a. 输出最短路径矩阵（起始节点为）s = 1 1 1 1 1 1 1 0 2 3 4 3 3 3 0 0