Dijkstra最短路径算法的优化和改进

《Dijkstra最短路径算法的优化和改进》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本科毕业设计（论文）Dijkstra最短路径算法的优化和改进学生姓名：。指导教师：屹专业、班级：信息院（系）：理2013年6月吉林摘要摘要随着计算机和地理信息科学的发展，GIS（地理信息系统）的应用领域越来越广．最短路径分析是GIS地理网络分析功能中的一个关键性的问题．计算最短路径的经典算法之一就是Dijkstra算法，许多工程中解决最短路径问题都是采用这种算法．然而，传统的Dijkstra算法在求解节点间最短路径时，对已标识节点外的大量节点进行了计算，从而影响了算法的速度．该算法的主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止．D

2、ijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍．本文在传统Dijkstra算法的基础上，对其进行了优化，此优化算法只对最短路径上节点的邻点做了一些处理，从而不涉及到其他的一些节点．提出的优化算法在更新最短路径值与选择最短路径值最小的节点时，仅仅涉及到节点的邻居集合及已标识集合中所有节点的邻居集合与已标识集合的差集，其运行时间取决于转接点的邻居集合的元素数量多少．通过减小算法中成功搜索的搜索范围和改进算法的存储结构这两个主要的研究方向使算法得到优化．因而，此优化算法在计算的节点数较传统算法大幅减少，提高

3、了算法的速度．本文通过实验和实际应用对改进后的算法进行了简单的验证．之后将一些算法的改进和实际例子相结合，这样就能使文章中算法的优化更为理想．关键词最短路径；Dijkstra；优化算法-I-目录AbstractWiththedevelopmentofcomputerandgeographicinformationscience,theapplicationsofGIS(GeographicInformationSystem)arebecomingmoreandmorewidely.However,shortestpathanalysisist

4、hekeyproblemofnetworkanalyses,Dijkstraalgorithmisaclassicarithmeticfortheshortestpath.Itistheacademicfoundationthatmanyengineeringsweresolvedintheshortestpathisuse.WhenashortestpathbetweennodesissearchedwithDijkstraalgorithm,alotofnodesawayfromlaggednodesareinvolved,sothatt

5、heefficiencyofDijkstraalgorithmislow.Mainfeaturesofthealgorithmisthestartingpointasthecenteroutwardexpansionlayersuntilitextendedtotheendpoint.Dijkstra'salgorithmisveryrepresentativeoftheshortestpathalgorithm,inmanyprofessionalcoursesinthebasiccontentasdescribedindetail.The

6、proposedalgorithmupdatestheshortestpathinthevalueoftheminimumvalueoftheshortestpathtothenode,onlythesetofneighborsofthenoderelatedtotheidentifiedsetandaneighborsetofallnodesintheidentifiedsetwiththesetdifference,itsrunningtimedependstransferthecontactelementsofthesetofneigh

7、borsofquantity.Successfulsearchalgorithmbyreducingthesearchrangeandimprovedalgorithmstoragestructureofthesetwomainresearchdirectionstooptimizethealgorithm.Therefore,thenumberofprocessednodesislargelyreducedintheoptimizationalgorithm,andefficiencyoftheoptimizationalgorithmis

8、improved.Theimprovedalgorithmisprovedtobecorrectandefficientbyexperimentsandpracti