利用MATLAB实现Dijkstra算法

利用计算机语言编程实现D算法一：实验目的本实验课程主要目的是让学生够熟练掌握图论中的D算法。二：实验方法选择MATLAB语言编程实现D算法。三：实验要求1.输入必要参数，包括：节点个数、节点间路径长度、给定节点；2.输出给定节点到其它各节点的最短路径、径长；3.节点间路径长度用矩阵形式表示。四：实验内容无向图共有7个节点，如下图所示。v1v2v6v3v4v5v7613245784计算机输入的节点间路径长度为7×7矩阵：123456712345670123106205430454076408780vvvvvvvvvvvvvv若1v为指定节点，则1v到其它各节点的最短路径及径长的计算机计算结果为：节点1v2v3v4v5v6v7v最短路径1{}v12{,}vv13{,}vv14{,}vv135{,,}vvv136{,,}vvv1367{,,,}vvvv径长01237614提示：不相邻的两个节点间可以用相对较大的数代替（如输入100表示）五：实验原理1.D算法原理已知图G=(V,E)，将其节点集分为两组：置定节点集pG和未置定节点集pGG。其中pG内的所有置定节点，是指定点sv到这些节点的路径为最短（即已完成最短路径的计算）的节点。而pGG内的节点是未置定节点，即sv到未置定节点距离是暂时的，随着算法的下一步将进行不断调整，使其成为最短径。在调整各未置定节点的最短径时，是将pG中的节点作为转接点。具体地说，就是将pG中的节点作为转接点，计算（sv,jv）的径长（jpvGG），若该次计算的径长小于上次的值，则更新径长，否则，径长不变。计算后取其中径长最短者，之后将jv划归到pG中。当（pGG）最终成为空集，同时pGG，即求得sv到所有其他节点的最短路径。jw表示sv与其他节点的距离。在pG中，iw表示上一次划分到pG中的节点iv到sv得最短路径。在pGG中，表示sv到jv（jpvGG）仅经过pG中的节点作为转接点所求得的该次的最短路径的长度。如果sv与jv不直接相连，且无置定节点作为转接点，则令jw=。2.D算法实现流程D算法流程如下图所示。在G-Gp中找到点vj，使vs到点vj的距离最小，并将vj划归到Gp以新Gp中的节点作为转接点，计算并修改（G-Gp）中的wj将vi划归到Gp中，即新的iv,svGp，sidiwvj与vs直连且未置定节点标值ijj=dwGp={vs}ws=0设，未置定节点集；G-Gp，vj∈G-Gp，s与j直接相连vj∈G-Gp，s与j不直接相连minjPsisjvG-Gd=dY重计算G-Gp中的wj的暂置值——修改wj值。中的各个节点的最短径可能经vi转接（或不转接），重新对（G-Gp）中的wj值取G-Gp选定所有w*j的最小值，并将其划归到Gp中：得到新的Gp，pG=n所有节点被置定，算法终止N*=min()jpipjiijvG-GvGjww,w+d*minjjpivG-Gw=w六：例题的计算过程表1D算法计算过程迭代次数1234567{,,,,,,}vvvvvvv置定节点iwGp0{0,1,2,3,,,}1v1w=01{}v1{,(1),2,3,,6,}2v2w=112{,}vv2{,,(2),3,7,6,}3v3w=2123{,,}vvv3{,,,(3),7,6,}4v4w=31234{,,,}vvvv4{,,,,7,(6),14}6v6w=612346{,,,,}vvvvv5{,,,,(7),,14}5v5w=7123465{,,,,,}vvvvvv6{,,,,,,(14)}7v7w=141234567{,,,,,,}vvvvvvv表21v到其他各节点的最短路径和径长节点1v2v3v4v6v5v7v最短路径1{}v12{,}vv13{,}vv14{,}vv136{,,}vvv135{,,}vvv1357{,,,}vvvv径长01236714七:仿真过程1.输入参数：a.输入无向图的节点个数提示：‘Pleaseinputnumberofthenotes: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,100,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.输出最短路径矩阵（起始节点为1v）s=1111111023433300006560000007c.输出对应的路径长度（与s顺序对应）d=012367143.运行结果截屏