Dijkstra算法求解最短路径的设计与实现

ComputerKnowledgeandTechnology电脑知识与技术软件设计开发本栏目责任编辑：谢媛媛第8卷第12期(2012年4月)Dijkstra算法求解最短路径的设计与实现刘敏（合肥学院计算机科学与技术系，安徽合肥230601）摘要：对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径的Dijkstra算法。对所设计的图的数据结构，提供必要的基本功能。建立图的表示模块，顶点的插入和删除操作模块；在建立图之后从单源点开始求最短路径并显示。实现的功能有建立有向图，排除和增加目的地，方便找出最短路径，在建立好的有向图中，显示出来从顶点到各个顶点的最短路径。关键词：最短路径；有向图；数据结构中图分类号：TP313文献标识码：A文章编号：1009-3044(2012)12-2759-031设计问题的提出1.1对于最短路径问题最短路径是在实际应用中非常有用的工具，将该问题细分，可以分为点到点最短路径，单源点的最短路径，所有点到所有点以及带负边情况下的最短路径。1.2Dijkstra算法的主要思想Dijkstra算法的基本思路是：假设每个点都有一对标号(dj,pj)，其中dj是从起源点s到点j的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：1)初始化。起源点设置为：①ds=0,ps为空;②所有其他点:di=∞,pi=?;③标记起源点s，记k=s,其他所有点设为未标记的。2)检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：dj=min［dj,dk+lkj］式中，lkj是从点k到j的直接连接距离。3)选取下一个点。从所有未标记的结点中，选取dj中最小的一个i：di=min［dj,所有未标记的点j］点i就被选为最短路径中的一点，并设为已标记的。4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j*5)标记点i。如果所有点已标记，则算法完全退出，否则，记k=i，转到2)再继续。2概要设计在任意图中实现求最短路径问题,首先是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径，所以，建立图这一步很关键。在实际使用当中，顶点的信息是成千上万，而且是随时可能产生变动，故建图模块要实现顶点的删除和插入操作；在完成了图的建立之后，用Dijkstra算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能，这也是程序实际化的要求。3建图过程能把一个带有顶点和权值的数据结构图输入电脑首先要用到数组，存储每个顶点信息以及每两个顶点构成的线路的权值。在建图的过程中，图的信息不是一成不变的，所以在实现初步输入图的信息后，要有删除和插入操作。需要插入顶点的时候，回归到初始建图模块，但是这个操作是在已建立的图上操作，而非在清除内存之后进行插入，所以，要实现插入的高效和实用性。在删除顶点的时候，在已建立的图上进行删除，首先对图进行遍历，只要是和欲删除的顶点有关联的边值都要删除掉，这样就实现了顶点的删除操作，目的是提高用户使用程序的效率，对已知或者误录入的顶点进行排除，增加了程序的人性化。4Dijkstra求最短路径的基本思想把顶点分成两组，第一组是已确定最短路径的结点的集合，第二组是尚未确定最短路径的结点的集合。按路径长度递增的次序逐个把第二组的顶点放到第一组中。设求从v1到其它各顶点间的最短路径,则在任意时刻，从v1到第一组各顶点间的最短路径都不大于从v1到第二组各顶点间的最短路径。4.1Dijkstra求最短路径的步骤设图以邻接矩阵cost存储，矩阵中各元素的值为各边的权值。顶点间无边时其对应权值用无穷大表示。从顶点v1到其它各顶点间的最短路径的具体步骤如下：收稿日期：2012-03-05E-mail:[e-mail]电脑知识与技术Vol.8,No.12,April2012.2759ComputerKnowledgeandTechnology电脑知识与技术本栏目责任编辑：谢媛媛软件设计开发第8卷第12期(2012年4月)1）初始化：s[MAX]。设一dist向量，其下标是各顶点，元素值是顶点v0到各顶点的边的权值。若v0到某顶点无边，dist向量中的对应值为无穷大。2）选dist中最小的权值，将其顶点s[V0]加入s集合。3）修改从顶点V0到集合s[MAX]中各顶点的最短路径长度,如果dist[u]+cost[u][j]dist[j]则修改dist[k]为dist[k]=dist[u]+cost[u][j]4)重复（2）、（3）n-1次。由此求得v1到图上其余各顶点得最短路径。4.2存储结构体：用于存储经过的顶点和顶点数以及权值struct{intnum;intpnode[MAX];}path[MAX];//path为从V0到各顶点的最短路径4.3建图子函数：voidcreatgraph()//创建带权有向图{inti,j,s,e,len,contin=1;printf(请输入点个数:);scanf(%d,&n);for(i=0;in;i++){for(j=0;jn;j++){cost[i][j]=up;cost[j][i]=up；}cost[i][i]=0;}4.4显示所建的邻接矩阵图voiddisplay(intn1)//显示用户输入的信息{inti,j;printf(\n********所建图的邻接矩阵*******\n____);for(i=0;in1;i++)printf(____%d____,i);printf(\n);for(i=0;in1;i++){printf(%d,i);for(j=0;jn1;j++)printf(\t%6d%d,%d,cost[i][j],i,j);printf(\n);4.5求最短路径模块voidshortdjs()//求最短路径{ints[MAX];intmindis,dis,i,j,v0=0,u=0;for(i=0;in;i++)//初始化{dist[i]=cost[v0][i];//初始化dist[]数组path[i].pnode[0]=v0;//顶点都为0path[i].num=0;//记录经过的结点数都为0s[i]=0;}4.6输出最短路径voiddispath()//输出最短路径{{printf((V0-%d):,i);if(dist[i]up)printf(\t%d\t(,dist[i]);elseprintf(\t∝\t();//显示无穷大for(j=0;jpath[i].num;j++)2760ComputerKnowledgeandTechnology电脑知识与技术软件设计开发本栏目责任编辑：谢媛媛第8卷第12期(2012年4月)printf(V%d-,path[i].pnode[j]);printf(V%d\n,path[i].pnode[path[i].num]);}}在这里还没有设计建图过程中，顶点的插入和删除功能，这两个功能可加到Creargraph（）中。5结束语这个程序广泛用在社会交通当中，用v0~V20表示不同的地点信息，供出行者参考，具体使用方法如下：1）输入顶点个数：最大不能超过20，请输入罗马数字，若输入其他符号，会显示警告；2）以“数字数字数字”的格式输入图的信息，第一次输入的第一个数字为源点，也就是我们的出发点，求最短路径会从这个顶点开始，每一次输入的第二个数字也是顶点，第三个数字是前两个顶点间的距离，或者说是权值，当输入“000”时，将停止录入功能；3）在录入图的信息之后，屏幕中会出现一个矩阵来核实用户录入的图正确与否，程序将会提示用户是否进行添加顶点，如果想添加顶点请按“Y”或者“y”，若不添加顶点请按“N”或“n”退出添加顶点系统；4）添加顶点的过程和Step1中录入方式相同，同样以“000”结束录入。这时系统将提醒用户是否要删除顶点，以防止误入图的信息；5）类似于Step3中方法进入删除顶点信息，系统根据用户输入的顶点序号删除其对应的所有信息，在完成修改之后系统将显示顶点到其他各点的最短路径，以供用户查询参考。参考文献：[1]王昆仑,李红.数据结构与算法[M].北京：中国铁道出版社,2006.[2]苏仕华.数据结构与算法解析[M].合肥:中国科学技术大学出版社,2004.[3]王昆仑,李红.数据结构与算法[M].北京:中国铁道出版社,2007.[4]郭嵩山.国际大学生程序设计竞赛例题解[M].北京:电子工业出版社,2008.[5]刘大有,唐海鹰.数据结构[M].北京:高等教育出版社,2001.[6]徐孝凯.数据结构实用教程[M].北京:清华大学出版社,1999.[7]严蔚敏,陈文博.数据结构及算法教程[M].北京:清华大学出版社,2001.[8]刘振安,刘燕君.C程序设计课程设计[M].北京:机械工业出版社,2004.[9]胡学钢.数据结构与算法设计指导[M].北京:清华大学出版社,1999.（上接第2742页）4结束语重视优质教学资源和网络信息资源的利用，把现代信息技术作为提高教学质量的重要手段，不断推进教学资源的共建共享，提高优质教学资源的使用效率，扩大受益面，是高职教育改革的要求。项目化教学支撑平台的建立，方便了教师对项目化课程教学的组织和实施，也为学生自主学习提供一个环境。在每个项目完成后，自动生成完整的课程教学资源包，为同类课程的教学提供有力的支持和参考。同时，还可以与其他高职院校联合共享支撑平台，将优质教学资源进行整合，根据专业将课程进行归类，形成专业教学资源包。并将这些教学资源整合到教学资源网中，与其他高等职业院校共享教学资源。参考文献:[1]余胜泉.典型教学支撑平台的介绍[J].中国远程教育，2001(2):57-61.[2]贺东光，孙博文，孙百瑜.网络教学协作学习模式的设计与实现[J].计算机教育，2010（2）:90-93.[3]宣华，郭大勇.试论高校现代化教学支撑平台的建设[J].教育理论与实践，2009,29(6):3-5.[4]郭春燕，杨波.基于网络的教学支撑平台的设计与研究[J].济南大学学院:自然科学版，2004,18(1):72-75.[5]芦明明.云计算支持的Web2.0在教育中的应用[J].软件导刊:教育技术，2010(5):45-46.2761