基于DIJKSTRA的最短路径搜索算法的优化及应用论文.doc

《基于DIJKSTRA的最短路径搜索算法的优化及应用论文.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、毕业设计（论文）题目基于Dijkstra的最短路径搜索算法的优化及应用姓名学号专业班级指导教师分院完成日期摘要最短路径分析是GIS地理网络分析功能中的一个关键问题。Dijkstra算法是计算最短路径的经典算法，是许多工程解决最短路径问题的理论基础。传统Dijkstra算法在求解节点间最短路径时，对已标识节点以外的大量节点进行了计算，从而影响了算法的速度。本文在对传统Dijkstra算法分析的基础上，对其进行了优化，优化算法只对最短路径上节点的邻居做了处理，而不涉及到其他节点。因此，在优化算法中计算的节点数大幅减少，提高了算法的速度。本文通过实验和实际应用对改

2、进后的算法进行了验证。关键词：最短路径；Dijkstra算法；优化AbstractShortestpathanalysisisthekeyproblemofnetworkanalyses，Dijkstraalgorithmisaclassicarithmeticfortheshortestpath.Itistheacademicfoundationthatmanyengineeringsweresolvedintheshortestpathissue.WhenashortestpathbetweennodesissearchedwithDijkstraalg

3、orithm，alotofnodesawayfromlaggednodesareinvolved，sothattheefficiencyofDijkstraalgorithmislow．AnoptimizationalgorithmispresentedinthispaperbasedonanalysisofDijkstraalgorithm．Onlythesenodesthattheneighborofnodesintheshortestpathareprocessed，andothernodesarenotprocessed.Therefore，then

4、umberofprocessednodesislargelyreducedintheoptimizationalgorithm，andefficiencyoftheoptimizationalgorithmisimproved．Theimprovedalgorithmisprovedtobecorrectandefficientbyexperimentsandpracticalapplication.Keywords:theshortestpath；Dijkstraalgorithm；optimization目录摘要IAbstractII第1章概述11.1国

5、内外最短路径算法概况11.1.1国内外最短路径研究的主流与方向11.1.2国内外主流算法及其简要展开21.1.2.1A*算法[3]21.1.2.2遗传算法[4]21.1.2.3Dijkstra算法31.1.3经典Dijkstra算法存在的问题41.2研究的意义41.3本文研究目标和内容4第2章Dijkstra经典算法研究62.1Dijkstra算法的原理及应用62.1.1Dijkstra算法原理62.1.2Dijkstra算法应用72.1.3Dijkstra算法的优缺点102.2以Dijkstra算法为基础算法进行优化的原因122.2.1Dijkstra算法

6、与其他主流算法的比较[5]122.2.1.1搜索速度比较122.2.1.2搜索成功率比较13第3章Dijkstra优化算法研究143.1多种Dijkstra优化算法的研究[6]143.1.1第一类优化算法——减小算法中成功搜索的搜索范围143.1.2第二类优化算法——改进算法的存储结构143.2本文对Dijkstra优化算法的研究153.2.1优化算法的目标153.2.2优化算法思路153.2.3优化算法描述163.2.4优化算法的特点203.3优化Dijkstra算法与原Dijkstra经典算法比较20第4章优化Dijkstra算法的应用214.1优化算法

7、在上海市物流中的实现214.1.1地图说明214.1.2属性数据库设计224.1.3算法实现234.1.4算法优化前后对比25第5章总结与展望265.1全文总结265.2展望26参考文献27附录29致谢35第1章概述1.1国内外最短路径算法概况1.1.1国内外最短路径研究的主流与方向最短路径这一重要问题早在20世纪初就已经得到人们的高度重视，当时也有许多科学家研究这一重要问题的求解方法。但直到1959年荷兰计算机科学家EdsgerWybeDijkstra(迪杰斯特拉)才给出这一问题求解的基本思想，并给出了算法。当时的Dijkstra提出的这一算法主要解决的问

8、题是从固定的一个点到其他各点的最短路径问题。后来这个