迪杰斯特拉最短路径算法

1、最短路径Dijkstra算法=f最课程设计的目的为了巩固“数据通信与通信网技术”课程学到的相关知识，通过对本课程所学知识 的综合运用，使学生融会贯通课程中所学的理论知识，初步掌握通信网络的体系结构和 扩频通信系统等相关知识；加深对通信网络的基本理论、基本知识和常用技术的理解； 提高学生分析问题的能力和实践能力，培养科学研究的独立工作能力。设计方案论证本次课程设计，我采用了 eclipse-Java软件，利用迪杰斯特（Dijkstra）算 法，来解决最短路径问题。迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于 1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路 径算法，解

2、决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为 中心向外层层扩展，直到扩展到终点为止。Eclipse是一个开放源代码的、基于Java的可扩展开发平台。就其本身而言，它只是 一个框架和一组服务，用于通过插件组件构建开发环境。幸运的是，Eclipse附带了一 个标准的插件集，包括Java开发工具（Java Development Tools，JDT）。Java是由Sun Microsystems公司于1995年5月推出的Java程序设计语言（以下简称Java语言）和Java 平台的总称。用Java实现的HotJava浏览器（支持Java applet）显示了 Java的魅力： 跨平

3、台、动态的Web、Internet计算。从此，Java被广泛接受并推动了 Web的迅速发展， 常用的浏览器现在均支持Java appleto另一方面，Java技术也不断更新，面向对象的 可视化集成编程系统。它不但具有程序框架自动生成、灵活方便的类管理、代码编写和 界面设计集成交互操作、可开发多种程序等优点，而且通过简单的设置就可使其生成的 程序框架支持数据库接口、OLE2, WinSock网络等。迪杰斯特拉算法介绍：迪杰斯特拉算法是典型最短路径算法，用于计算图或网中某个特定顶点到其他所有 顶点的最短路径。主要特点是以起始点为中心向外，层层扩展，直到扩展覆盖所有顶点。 设G=（V,E）为一个带全

4、有向图，把图中顶点集合V分成两组。第一组为已求出最短路径 的顶点集合。用S表示，初始时S中只有一个源点，以后每 求得一条最短路径，就将 所到达最短路径的顶点加入到集合S中，直到全部顶点都加入到S中。第二组为其余 未确定最短路径的顶点集合。用U表示，U=V-S，U中的顶点不断的加入到S中，直 到U为空，S=V。在U加入S的过程中，始终保持源点到S中各顶点的最短路径长度小 于或等于源点到U中任意顶点的最短路径长度。设计的过程与分析3.1 Dijkstra算法原理首先，引入一个辅助向量D，它的每个分量Di表示当前所找到的从起始点V （即源点V ）到其它每个顶点vi的长度。例如，D3 = 2表示从起始

5、点到顶点3的路径相对最小长度为2。这里强调相对 就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。D的初始状态为：若从V到V有孤（即从V到V 存在连接边），则D i 为孤上的权值（即为从V到Vi的边的权值）；否则置D i为8。显然，长度为 D j = Min D |Vi eV 的路径就是从V出发到顶点 七 的长度最短的一条路 径，此路径为（V,Vj） o那么，下一条长度次短的是哪一条呢？也就是找到从源点V到下一个顶点的最 短路径长度所对应的顶点，且这条最短路径长度仅次于从源点V到顶点Vj的最短路 径长度。假设该次短路径的终点是Vk ，则可想而知，这条路径要么是（VVk

6、 ）， 或者是（V,Vj,Vk ）。它的长度或者是从V到Vk的孤上的权值，或者是Dj加上从Vj至0 Vk的孤上的权值。一般情况下，假设S为已求得的从源点V出发的最短路径长度的顶点的集合，则可 证明：下一条次最短路径（设其终点为X ）要么是孤（V,X ），或者是从源点V出 发的中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的的最。课程设计说明书NO.3短路径长度必是D= Min D | V eV-S ，其中D要么是孤（V, V ）上的权jiiii值，或者是Dk （ VkeS）和孤（Vk , Vi）上的权值之和算法描述如下：1）令arcs表示孤上的权值。若孤不存在，则置arcs为

7、8 （在本程序中为MAXCOST）。 S为已找到的从V出发的的终点的集合，初始状态为空集。那么，从V出发到图上其 余各顶点Vi可能达到的长度的初值为D=arcsLocate Vex（G, Vi ）， Vi eV2）选择 Vj ，使得 Dj=Min（ D | V eV-S ；3）修改从V出发的到集合V-S中任一顶点Vk的最短路径长度。3.2问题描述在无向图G=（V,E）中，假设每条边Ei的长度为wi，找到由顶点V0到其余 各点的最短值。具体位置及距离分布如下图所示：13图1初始位置及距离3.3算法思想按路径长度递增次序产生算法：把顶点集合V分成两组：课程设计说明书NO.4（1） S：己求出的顶点

8、的集合（初始时只含有源点V0）（2） V-S=T:尚未确定的顶点集合将T中顶点按递增的次序加入到、中，保证：（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短 路径长度。（2）每个顶点对应一个距离值S中顶点：从V0到此顶点的长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是 从V0经S中顶点到Vk的路径权值之和。求最短路径步骤算法步骤如下：G=V,E初始时令S=V0,T=V-S=其余顶点，T中顶点对应的距离值若存在V0,Vi，d（V0,Vi）为V0,Vi孤上的权值若不存在V0,Vi

9、，d（V0,Vi）为8从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到、中对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距 离值缩短，则修改此距离值。重复上述步骤2、3,直到S中包含所有顶点，即W=Vi为止。3.4具体运算过程针对3.2中图1做出如下分析：最初 sptSetis 空集和距离指派给顶点0,INF, INF, INF, INF, INF, INF, INF , 正表明无限。现在选择顶点的最小距离值。顶点为0,包括sptSet。所以sptSet变成 了 0。包括0sptSet后，更新距离值的相邻的顶点。相邻的顶点0、1和7。1和7的 距离值更新为4和8。

10、下面的子图显示顶点和他们的距离值，只有有限的顶点的距离 值。图中包含的顶点SPT的用绿色表示。图2初次确定以结点0为出发点选择顶点的最小距离值和未包含在SPTsptSET中的位置点。选择并添加到sptSet 顶点1，所以sptSet现在变成了 0,1。更新相邻顶点的距离值为1。顶点的距离值2 变成12。412T图3第二次确定结点现选择顶点的最小距离值和未包含在SPTsptSET中的位置。现在sptSet变成了 0，1，7。更新与7相邻的顶点的最短距离值，与其相聚最近的距离值为6和8变得有限（分 别为15和9）。12选择顶点的最小距离值和未包含在SPTsptSET中的位置点。顶点6是选择。所以

11、sptSet现在变成了 0，1，7, 6。更新6相邻顶点的距离值。顶点的距离值5和8更 新。由于7和8之间的距离为7,而8和9之间距离为6,则更新之后为下图所示：1Z4佬4865911图5第四次确定的结点继续选择顶点最小的和不包含SPTsptSET的位置点，在考虑到8和6之间的距离为6, 而8和2之间距离为2，自然将8与2相连，在2和5为顶点，将3和4以最短距离分别 连到2和5上，于是得到下图所示位置关系：根据以上的迪杰斯特拉绘图算法的优点是:思想非常明确；过程简单明了；十分容易接受：表1 Dijkstra算法计算过程步骤ND(1)D(2)D(3)D(4)D(5)D(6)D(7)D(8)初始0

12、4888888810,1,74(8)8888(8)820,1,2,6,74121988(9)81430,1,2,5,6,7412198(11)981440,1,2,5,6,7,841219281198(14)50,1,2,3,5,6,7,8412(19)2811981460,1,2,3,4,5,6,7,841219(21)1198143.5 java语言对Dijkstra算法的实现以上算法比较简单明了，但毕竟这是一个很机械的操作，我们可以借助机器来做这些 简单的操作，我们的任务是只需将对应位置的矩阵写入相应的代码即可，借助机器语言将 其迅速的计算出来。课程设计说明书NO.7本次课设所使用的是运

13、用Java语言将上面所述的问题计算出来，在进行分析得出来 最佳解决途径。具体Java语言代码如下：/ A Java program for Dijkstras single source shortest path algorithm./ The program is for adjacency matrix representation of the graphimport java.util.*;import java.lang.*;import java.io.*;class ShortestPath/ A utility function to find the vertex with

14、 minimum distance value,/ from the set of vertices not yet included in shortest path treestatic final int V=9;int minDistance(int dist, Boolean sptSet)/ Initialize min valueint min = Integer.MAX_VALUE, min_index=-1;for (int v = 0; v V; v+)if (sptSetv = false & distv = min)min = distv;min_index = v;r

15、eturn min_index;void printSolution(int dist, int n)System.out.println(Vertex Distance from Source);for (int i = 0; i V; i+)System.out.println(i+ tt +disti);/ Funtion that implements Dijkstras single source shortest path/ algorithm for a graph represented using adjacency matrix/ representationvoid di

16、jkstra(int graph, int src)int dist = new intV; / The output array. disti will hold/ the shortest distance from src to i/ sptSeti will true if vertex i is included in shortest/ path tree or shortest distance from src to i is finalized Boolean sptSet = new BooleanV;/ Initialize all distances as INFINI

17、TE and stpSet as false for (int i = 0; i V; i+)disti = Integer.MAX_VALUE;sptSeti = false;/ Distance of source vertex from itself is always 0 distsrc = 0;/ Find shortest path for all verticesfor (int count = 0; count V-1; count+)/ Pick the minimum distance vertex from the set of vertices/ not yet pro

18、cessed. u is always equal to src in first / u = minDistance(dist, sptSet);/ Mark the picked vertex as processed sptSetu = true;/ Update dist value of the adjacent vertices of the / picked vertex.for (int v = 0; v V; v+)/ Update distv only if is not in sptSet, there is an/ edge from u to v, and total

19、 weight of path from src to / v through u is smaller than current value of distvif (!sptSetv & graphuv!=0 &distu != Integer.MAX_VALUE &distu+graphuv 10-2120-1-20-3190-1-2-30-4210-7-6-5-40-5110-7-6-50-690-7-60-780-70-8140-1-2-8由以上表格根据其路线依然可以得出图6的结果。同时结论得以验证。这个算法的具体内容分析如下：以上为具体的实现代码，由于代码数量比较大，在eclipse

20、上调试过程总会有点错误或 者小瑕疵。因此调试需要花费耐心和细心，由于eclipse自带的检错功能，操作者可以 减少很多检错的时间。其实，我就是看中它的这一点才选用Java语言来实现这一方法， 但在操作过程中仍然遇到了一些麻烦，在老师和同学的帮助下都解决了。代码的9-22行表示一个效用函数与最小距离值，找到顶点从顶点的集合不包含在最 短路径树；26-31是一个for循环，定义一个效用函数与最小距离值，找到顶点从顶点的集合不 包含在最短路径树；36-53是定义一个方法计算到各个节点的距离；56-76定义另一个for循环方法选择的最小距离顶点的顶点，若是没有确定就一直 循环；84-99是主方法，将要

21、处理的数据转化为矩阵，并调用ShortestPath类中的方法， 运算并输出从0节点到各个节点之间的最短距离。此算法只能求出给定两点之间的最短路径，若要求任意两点问最短路径，则需轮流 以每一个顶点为源点，重复执行Dijkstra算法8次。重复执行需要重新计算分析矩阵，比较复杂。Dijkstra算法的优点是：实现了把简单反复计算的过程由机器来操作；用户只需知道初始的各个节点位置模型数据即可；该算法的核心思想比较经典明了；计算快捷、方便、效率高；Dijkstra算法的缺点是：编写代码比较繁琐；需要有一定的计算机语言基础；调试代码需要认真细心该算法不能进行负权运算；综上全面总结Dijkstra算法的

22、特点：Dijkstra（迪杰斯特拉）算法是典型的最短路径路由算法，用于计算一个节点 到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩 展到终点为止。所以根据Dijkstra算法能得出最短路径的最优解。Dijkstra算法是典型的算法，而且是很有代表性的算法。Dijkstra 一般的表述通 常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均 采用永久和临时标号的方式。注意该算法要求图中不存在负权边。最短路径问题的求解还不止这一种算法，比如还有分枝定界等等，而且大家也可以 创造出各种各样的新算法来。不同的最短路径问题到底用哪种算法，以及还需

23、要对该种 算法作什么改动，是非常重要的，这种能力往往是很多同学所欠缺的，这需要大家在平 常的训练中多做这类题目，还要多总结，以达到熟能生巧的境界。最短路径问题的求解还不止这一种算法，比如还有分枝定界等等，而且大家也可以 创造出各种各样的新算法来。不同的最短路径问题到底用哪种算法，以及还需要对该种 算法作什么改动，是非常重要的，这种能力往往是很多同学所欠缺的，这需要大家在平 常的训练中多做这类题目，还要多总结，以达到熟能生巧的境界Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内 容有详细的介绍。根据设计结果我们可以知道，如果从某顶点出发（此点称为源点）， 经边到达另一顶

24、点（称为终点）的路径不止一条，而如何找到一条路径使沿此路径上各 边的权值之和为最小就是我们研究的问题。4、设计体会在此期间我也失落过，也这已经不是第一次做课设了，每一次做课设都是一次新的 挑战，每次都能学到新的知识，获得新的技能。我觉得入门还是多看些书，多实践，养 成良好的习惯，在实践的同时多思考问题，多看别人优秀的解题思路与方法，多看别人 优秀的代码，尝试自己去实现或者说模仿着去实现，理论联系实际的能力还急需提高。 在这次的课程设计中不仅检验了我所学习的知识，也培养了我如何去把握一件事情，如 何去做一件事情，又如何完成一件事情。在设计过程中，与同学分工设计，和同学们相 互探讨，相互学习，相互

25、监督。学会了合作，学会了宽容，学会了脚踏实地。所谓课程设计就对是我们专业课程知识综合应用的实践训练，是对我们所学的专业 知识的检验。说真心话，课设是让我们巩固学习的知识，从而学到更多知识。并不是让 我们全部照抄别人的东西，只有真的进行课程设计，学会脚踏实地迈开这一步，才能为 明天能稳健地在社会大潮中奔跑打下坚实的基础。谁也不是生来就是天才，总有不会或 不懂的地方，总要去学习，去犯错，去改正，这一过程就是我们成长，增长能力的过程。 所以，不要总是想着依靠别人，让别人帮忙。这不是一个真正大学生的作为，所有遇到 的事，都要学会面对，学会接受。从开始时满富盛激情到最后汗水背后的复杂心情，点点滴滴无不令

26、我回味无长。通过 这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只 有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而 提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难 重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自 己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，比如说VC+的运 行、编译过程。使用VC+实现了 Dijkstra算法实现路由最短路径选择也不够透彻通过这 次课程设计之后，一定把以前所学过的知识重新温故。这样不仅做到温故知，新更重要的 是能更熟练

27、的掌握学过的知识！Dijkstra算法是很多最短距离算法的一种，也是相当经典的一种算法。在很多领域中 都起着重要作用，比如说管道铺设、电话线的安装、货物运送等的路线选择。当算法中的 元素比较少时，我们可以直接在书面上计算。当元素够多时，这就需要借助计算机，我们 学习到的算法一般只给出了理论而没有进行程序实现，因此笔者对他们分别进行了程序实 现，希望在实际生活中能给大家带来方便。最终课程设计总算完成了，在设计中遇到了很多问题，最后在老师的辛勤指导下，问 题终于迎刃而解。同时，在老师的身上我学得到很多实用的知识，在此表示感谢！让我对 所学的书本上的知识得到了实际上的应用，这不仅使我对知识的记忆更加牢固，还让我对 有关通信网基础里的最短路径算法有了更深的了解，让我了解到，我们平常所学的知识不 是死的，我们在日常中也可以用到。通过这次的学习，让我对通信网基础这门课程更加感 兴趣了。在这期间，我们同学间互相帮助，互相讲解不会的地方，让我们真正在快乐中学 习到了知识。课程设计是培养学生综合运用所学知识，发现，提出，分析和解决实际问题，锻 炼实践，我想我们一定会抓住每一次这种学习的机会，更加努力！在我看来，掌握几门基础的计算机语言很重要，特别是C语言、C+、Java等语言是非 常重要的，本次课设我