《基于Dijkstra的最短路径算法的优化及应用》由会员分享，可在线阅读，更多相关《基于Dijkstra的最短路径算法的优化及应用（35页珍藏版）》请在金锄头文库上搜索。
1、本科学生毕业论文论文题目：基于Dijkstra的最短路径算法的优化及应用学 院：年 级：专 业：姓 名：学 号：指导教师：2011年5月20日摘要随着计算机和地理信息科学的发展，GIS（地理信息系统）的应用领域越来越广。最短路径分析是GIS地理网络分析功能中的一个关键性的问题。计算最短路径的经典算法之一就是Dijkstra算法，许多工程中解决最短路径问题都是采用这种算法。然而，传统的Dijkstra算法在求解节点间最短路径时，对已标识节点外的大量节点进行了计算，从而影响了算法的速度。本文在传统Dijkstra算法的基础上，对其进行了优化，此优化算法只对最短路径上节点的邻居做了一些处理，从而不涉
2、及到其他的一些节点。故而，此优化算法在计算的节点数较传统算法大幅减少，提高了算法的速度。本文通过实验和实际应用对改进后的算法进行了简单的验证。关键词最短路径；Dijkstra；优化算法AbstractWith the development of computer and geographic information science,the applications of GIS (Geographic Information System) are becoming more and more widely.However, shortest path analysis is the key
3、 problem of network analyses,Dijkstra algorithm is a classic arithmetic for the shortest path.It is the academic foundation that many engineerings were solved in the shortest path is use.When a shortest path between nodes is searched with Dijkstra algorithm,a lot of nodes away from lagged nodes are
4、involved,so that the efficiency of Dijkstra algorithm is low.An optimization algorithm is presented in this paper based on analysis of Dijkstra algorithm.Only these nodes that the neighbor of nodes in the shortest path are processed,and other nodes are not processed.Therefore,the number of processed
5、 nodes is largely reduced in the optimization algorithm,and efficiency of the optimization algorithm is improved.The improved algorithm is proved to be correct and efficient by experiments and practical application.Key wordsthe shortest path；Dijkstra；optimizationalgorithmI目录摘要IAbstractII第一章 绪论1一、国内外
6、最短路径算法的发展及其概况1二、传统Dijkstra算法仍然存在的一些问题1三、本文研究的内容及意义2第二章 Dijkstra经典算法3一、原理及应用3（一）原理3（二）应用4（三）优缺点7二、Dijkstra算法与其他主流算法的比较9（一）搜索速度比较9（二）搜索成功率比较10第三章 基于Dijkstra算法的优化算法的研究12一、几种优化算法12（一）减小算法中成功搜索的搜索范围12（二）改进算法的存储结构12二、本文对Dijlstra优化算法研究12（一）目标13（二）思路13（三）描述14（四）特点17三、本文优化算法与传统算法的比较18第四章 此优化算法在消防中的相关应用19一、消防
7、力量调集路径最优指标的选取19二、Dijkstra最短路径经典算法及分析20（一）问题定义20（二）Dijkstra算法20（三）Dijkstra算法优化及分析201优化Dijkstra算法的思路202优化Dijkstra算法的描述21结论22参考文献23附录一24致谢31第一章 绪论一、国内外最短路径算法的发展及其概况最短路径在20世纪初开始受到人们的重视，关于它的求解方法，当时有很多科学家在研究。但给出求解的基本思想的人直到1959年才出现，是一位名叫Edsger Wybe Dijkstra (迪杰斯特拉)的荷兰计算机科学家，他不仅给出了求解的基本思想，还给出了算法。他给出的算法主要解决的
8、问题是从某一个固定的点到其他各点的最短路径问题。后来这个算法被誉为一代经典，被称作Dijkstra算法。后来，人们逐渐从两个方面来研究最短路径，分为完全信息情况下和不确定情况下。确定情况下对最短路径的研究的过程中，发展出了很多高效的算法，其中1958年的Bellman算法、1959年的Dijkstra算法、1969年的Dreyfus算法已成为确定情况下的经典算法1。而不确定情况下对最短问题的研究又分成了四个方面：研究路段长度随机变化的最短路径问题，以Frank和Mirchandani为代表；研究不同费用函数最短路径问题，以Loui、Muethy和Sarkar为代表；研究时间独立情况下的路段长度
9、随机变化的最短路径问题，Hall、LiPing Fu、L.R.Rilett、Elise和Hani为代表；研究路段长度为区间范围的最短路径问题，以Tomas和Rajeev为代表。其中，第二方面问题的研究得出的结论是“当目标是期望最短路径时问题转化为将边的权重用期望值表示的最短路径问题”。二、传统Dijkstra算法仍然存在的一些问题 原始Dijkstra算法在存储图形数据和运算时，基于网络的权矩阵，需要根据其节点与距离之间的关系，形成关联矩阵、邻接矩阵与距离矩阵，需要定义NN的数组来存储数据，其中N为网络的节点数，当网络的节点数较大时，将占用大量的计算机内存。 原始Dijkstra算法在运行时一
10、般将网络节点分为未标记节点、临时标记节点和永久标记节点3种类型。网络中所有节点首先初始化为未标记节点，在搜索过程中和最短路径节点相连通的节点为临时标记节点，每一次循环都是从临时标记节点中搜索距离原点路径长度最短的节点作为永久标记节点，直至找到目标节点或者所有节点都成为永久标记节点才结束算法。根据算法的描述可知对临时标记节点的遍历成为Dijkstra算法的瓶颈，影响了算法的执行效率。三、本文研究的内容及意义随着社会的不断进步，最短路径算法在人们的日常生活显得越来越重要。每天开车去上班，应该选择哪条公路才能使自己到公司的费用最低、时间最少，这是最短路径的问题；在网络路由中，怎样选择最优的路由路径，
11、这也是最短路径问题；在交通旅游、城市规划以及电网架设中怎样使其耗费的资金最少，这还是最短路径问题。由此可见对最短路径问题的研究是非常有意义的。最短路径算法是计算机科学与地理信息科学等领域研究的热点，其算法有很多种，其中传统的Dijkstra算法一般用于计算一个源节点到所有其他节点的最小代价路径，并且能够适应网络拓扑的变化，性能稳定，因而可以在运输路线规划等领域都应用广泛。第二章 Dijkstra经典算法 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍
12、历计算的节点很多，所以效率低2。一、原理及应用 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。（一）原理Dijkstra算法是1959年由EWDijkstra提出的图论中求最短路径的一个著名的
13、算法，使用其可以求得图中一点到其他各顶点的最短路径。原始的Dijkstra算法将网络结点分成3部分：未标记结点、临时标记结点和永久标记结点。网络中所有结点首先初始化为未标记结点，在搜索过程中和最短路径中的结点相连通的结点为临时标记结点，每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，直至找到目标结点或者所有的结点都成为永久标记结点来结束算法。假设每个点都有一对标号 (wj, pj)，其中wj 是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj 则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法
14、的基本过程如下：1)初始化。起源点设置为： ws=0, ps为空； 所有其他点: wi=, pi=?；标记起源点s，记k=s,其他所有点设为未标记的。2)检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：wj=minwj, wk+dkj 式中，dkj 是从点k到j的直接连接距离。3)选取下一个点。从所有未标记的结点中，选取wj中最小的一个i:wi=min wj，（所有未标记的点j），点i就被选为最短路径中的一点，并设为已标记的。4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点，设置：i=j*。5)标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2)再继续。 0 100 10 41 30
