毕业设计-基于dijkstra的最短路径搜索算法的优化及应用论文

毕业设计-基于dijkstra的最短路径搜索算法的优化及应用论文

ID:5465745

大小:800.01 KB

页数:49页

时间:2017-12-13

毕业设计-基于dijkstra的最短路径搜索算法的优化及应用论文_第1页
毕业设计-基于dijkstra的最短路径搜索算法的优化及应用论文_第2页
毕业设计-基于dijkstra的最短路径搜索算法的优化及应用论文_第3页
毕业设计-基于dijkstra的最短路径搜索算法的优化及应用论文_第4页
毕业设计-基于dijkstra的最短路径搜索算法的优化及应用论文_第5页
资源描述:

《毕业设计-基于dijkstra的最短路径搜索算法的优化及应用论文》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

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

2、大幅减少,提高了算法的速度。本文通过实验和实际应用对改进后的算法进行了验证。关键词:最短路径;Dijkstra算法;优化IIAbstractShortestpathanalysisisthekeyproblemofnetworkanalyses,Dijkstraalgorithmisaclassicarithmeticfortheshortestpath.Itistheacademicfoundationthatmanyengineeringsweresolvedintheshortestpathissu

3、e.WhenashortestpathbetweennodesissearchedwithDijkstraalgorithm,alotofnodesawayfromlaggednodesareinvolved,sothattheefficiencyofDijkstraalgorithmislow.AnoptimizationalgorithmispresentedinthispaperbasedonanalysisofDijkstraalgorithm.Onlythesenodesthattheneigh

4、borofnodesintheshortestpathareprocessed,andothernodesarenotprocessed.Therefore,thenumberofprocessednodesislargelyreducedintheoptimizationalgorithm,andefficiencyoftheoptimizationalgorithmisimproved.Theimprovedalgorithmisprovedtobecorrectandefficientbyexper

5、imentsandpracticalapplication.Keywords:theshortestpath;Dijkstraalgorithm;optimizationII目录摘要IAbstractII第1章概述11.1国内外最短路径算法概况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本文研究目标和内容

6、4第2章Dijkstra经典算法研究62.1Dijkstra算法的原理及应用62.1.1Dijkstra算法原理62.1.2Dijkstra算法应用72.1.3Dijkstra算法的优缺点102.2以Dijkstra算法为基础算法进行优化的原因122.2.1Dijkstra算法与其他主流算法的比较[5]122.2.1.1搜索速度比较122.2.1.2搜索成功率比较13第3章Dijkstra优化算法研究143.1多种Dijkstra优化算法的研究[6]143.1.1第一类优化算法——减小算法中成功搜索的搜索

7、范围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优化算法在上海市物流中的实现214.1.1地图说明214.1.2属性数据库设计224.1.3算法实现234.1.4算法优化前后对比25第5章总结与展望265.1全文总结265.2展望26

8、参考文献27附录29致谢35III第1章概述1.1国内外最短路径算法概况1.1.1国内外最短路径研究的主流与方向最短路径这一重要问题早在20世纪初就已经得到人们的高度重视,当时也有许多科学家研究这一重要问题的求解方法。但直到1959年荷兰计算机科学家EdsgerWybeDijkstra(迪杰斯特拉)才给出这一问题求解的基本思想,并给出了算法。当时的Dijkstra提出的这一算法主要解决的问题是从固定的一个点到其他各点的最短路径

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。