Dijkstra最短路径算法,非常适合相关专业的学生。
第25卷第3期2006年8月
文章编号:1006-4869(2006)03-0030-04
南昌工程学院学报
JournalofNanchangInstituteofTechnologyVo.l25No.3Aug.2006
Dijkstra最短路径算法优化
章永龙
(扬州大学信息工程学院,江苏扬州225009)
摘 要:传统Dijkstra算法在求解节点间最短路径时,对已标识节点以外的大量节点进行了计算,从而影响了算法的速度.在对传统Dijkstra算法分析的基础上,对其进行了优化,优化算法只对最短路径上节点的邻居做了处理,而不涉及到其他节点.因此,在优化算法中计算的节点数大幅减少,提高了算法的速度.关键词:最短路径;Dijkstra算法;优化中图分类号:TP301.6
文献标识码:A
OptimizationofDijkstraAlgorithm
ZHANGYong-long
(CollegeofInformationEnginneering,UniversityofYangzhou,Yangzhou225009,China)Abstract:WhenashortestpathbetweennodesissearchedwithDijkstraalgorithm,alotofnodesawayfromlaggednodesareinvolved,sothattheefficiencyofDijkstraalgorithmislow.Anoptimizationalgo-rithmispresentedinthispaperbasedonanalysisofDijkstraalgorithm.Onlythesenodesthattheneigh-borofnodesintheshortestpathareprocessed,andothernodesaren tprocessed.Therefore,thenumberofprocessednodesislargelyreducedintheoptimizationalgorithm,andefficiencyoftheoptimizationa-lgorithmisimproved.
Keywords:theshortestpath;Dijkstraalgorithm;optimization
0 引 言
实际生活中的许多问题都可归结于图论中的最短路径问题,如:电子导航、交通旅游、公交出行等.这里的最短路径不仅仅指地理意义上的距离最短,可引申为最少费用、最短时间、延时最短、吞吐量最大等约束条件.传统的最短路径算法,如Dijkstra算法
2
[1]
用来求解图上从任一节点(源点)到其余各节点的最短路径.其
时间复杂度为O(N);采用邻接矩阵存储网络拓扑结构,需要(N N)的存储空间,随着节点数N的增大,其
[2-5]
计算效率和存储效率越低.针对此问题,提出了Dijkstra算法的改进,本文在对传统Dijkstra算法分析的基础上,对其进行了优化,优化算法只对最短路径上节点的邻居做处理,而不涉及到其他节点.
1 传统Dijkstra算法
最短路径问题是指在一个非负权值图中找出两个指定节点间的一条权值和最小的路径.Dijkstra算法是经典的解决最短路径问题的算法,它可以找出指定节点到其他各个节点间的最短路径,其主要思想是首先从
收稿日期:2006-05-24
作者简介:章永龙(1976-),男,江西高安人,助教,硕士.
Dijkstra最短路径算法优化策略_其它_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 Dijkstra最短路径算法优化策略_其它_高等教育_教育专区。数模相关方法...
Dijkstra最短路径算法优化策略_IT/计算机_专业资料。Dijkstra最短路径算法优化策略第34 卷第 5 期 2009 年 9 月 测绘科学 Science of Surveying and M app ...
Dijkstra最短路径算法的优化和改进_天文/地理_自然科学_专业资料。随着计算机和地理信息科学的发展,GIS(地理信息系统)的应用领域越来越广.最短路径分析是GIS地理...
Dijkstra最短路径算法优化_IT/计算机_专业资料。硕士论文 路径优化第!% 卷第 , 期 !""# 年 + 月文章编号: ’""# $ &+#( !""#) $ ""," $ "&...
Dijkstra最短路径算法优化策略_计算机软件及应用_IT/计算机_专业资料。数模相关方法2009 年 10 月 第 35卷 第 10期 北京航空航天大学学报 Journal of Beijing ...
、一 最短路径与 Dijkstra 算法 顶点 ( Vertex) 和边 ( Edge ) 为基础 , 采用顶点分区和 记录绝对地址来优化 Dijkst ra 算法的方法 。设 G = ( V , E...
本文在传统 Dijkstra 算法的基础上,对其进行了优化,此优化 算法只对最短路径上节点的邻居做了一些处理,从而不涉及到其他的一些节点。故而, 此优化算法在计算的...
2 基于 Dijkst ra 算法的一种最短路径优化算法张福浩, 刘纪平, 李青元 ( 中国测绘科学研究院, 北京 100039) 摘要: 详细介绍了经典的 Dijkstra 算法, 举例说明...
求解最短路径问题常用的算法比较多,例如:Dijkstra 算法,A觹 算法等。 本文通过对传统的 Dijkstra 算法进行分析,提 出了对其优化和改进的方法。 2 Dijkstra 算法...
热门文档