最短路径算法中Dijkstra算法的优化及应用
时间:2017-04-11 13:20 来源:毕业论文 作者:毕业论文 点击:次
| 摘 要：计算最短路径的经典算法之一就是Dijkstra算法，它是解决工程中最短路径问题的基础。但是，传统的Dijkstra算法在求解节点间最短路径时，对已标识节点外的大量节点进行了计算，从而影响了算法的速度。本毕业论文在传统Dijkstra算法的基础上，对最短路径上节点的邻节点做了一些处理，从而不涉及到其他的一些节点。故而，此优化算法在计算的节点数较传统算法大幅减少，提高了算法的速度。本文通过实际应用对改进后的算法进行了简单的验证。7025 关键词：最短路径；Dijkstra算法；优化算法 Optimization and Application of Dijkstra Algorithm for the Shortest Path Abstract：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 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, Therefore,the number of processed nodes is largely reduced in the optimization algorithm,and efficiency of the optimization algorithm is improved. Key Words：the shortest path; Dijkstra algorithm; optimization algorithm 目 录 摘 要 1 引言 1 1.绪论 2 1.1 最短路径算法的研究现状 2 1.2 最短路径算法的研究意义 2 1.3 已有Dijkstra算法存在的问题 2 2.经典的Dijkstra算法 3 2.1 Dijkstra算法的思想 3 2.2 Dijkstra算法的步骤 4 3.优化的Dijkstra算法 6 3.1 两种Dijkstra优化算法 6 3.2 优化的Dijkstra算法 6 4.Dijkstra算法的应用 7 4.1 Dijkstra算法在城市建设选址中的应用 7 4.2 Dijkstra算法在医院间的应用 8 4.3 Dijkstra算法在交通系统中的应用 9 5.总结 10 参考文献 11 致谢 12 最短路径算法中Dijkstra算法的优化及应用引言 最短路径问题是图论中的一个重要问题, 在交通运输、物流配送、网络分析等方面都有着广泛的应用,求解最短路径的方法也有很多, 诸如动态规划法、启发式算法、迭代法等, 本文就经典的Dijkstra算法进行分析, 提出一种改进的算法,并对改进算法进行算法分析。 1.绪论 1.1最短路径算法的研究现状 最短路径在20世纪初开始受到人们的重视，关于它的求解方法，当时有很多科学家在研究。但给出求解的基本思想的人直到1959年才出现，是一位名叫Edsger Wybe Dijkstra (迪杰斯特拉)的荷兰计算机科学家，他不仅给出了求解的基本思想，还给出了算法。他给出的算法主要解决的问题是从某一个固定的点到其他各点的最短路径问题。后来这个算法被誉为一代经典，被称作Dijkstra算法。后来，人们逐渐从两个方面来研究最短路径，分为完全信息情况下和不确定情况下。确定情况下对最短路径的研究的过程中，发展出了很多高效的算法，其中1958年的Bellman算法、1959年的Dijkstra算法、1969年的Dreyfus算法已成为确定情况下的经典算法。而不确定情况下对最短问题的研究又分成了四个方面：研究路段长度随机变化的最短路径问题，以Frank和Mirchandani为代表；研究不同费用函数最短路径问题，以Loui、Muethy和Sarkar为代表；研究时间独立情况下的路段长度随机变化的最短路径问题，Hall、LiPing Fu、Lett.R.Ril、Elise和Hani为代表；研究路段长度为区间范围的最短路径问题，以Tomas和Rajeev为代表。其中，当目标是期望最短路径时,问题转化为将边的权重用期望值表示的最短路径问题。 (责任编辑：qin) |