基于Dijkstra算法的优化研究.docx

?

?

基于Dijkstra算法的优化研究

?

?

易文静田俊峰

摘要：最短路径算法的研究及其应用在各个领域都起着重要作用，例如交通领域的最优路线，军事领域的行军路线，网络通信领域的路由选择等。该文将对最短路径问题中最经典的Dijkstra（迪杰斯特拉）算法进行介绍和优化改进。笔者将这种优化改进后的算法称之为：DJ_ray算法，意思是对Dijkstra算法进行发散性思想优化。该文将会对传统的Dijkstra算法与优化后的DJ_ray算法，在思想、原理、实现方法、数据结构上进行说明比较，并从时间及其空间复杂度上进行分析对比。同时，为了更好地展示DJ_ray算法在实际应用中的优点，文本将以DJ_ray算法优化火车交通网络路线为案例来进行阐述。

关键词：最短路径；交通路线；Dijkstra算法；DJ_ray算法

：TP311：A：1009-3044（2016）23-0166-03

Abstract：Researchandapplicationoftheshortestpathalgorithmplaysanimportantroleineveryfield，suchastheoptimalrouteinthefieldoftransportation，travelrouteinthefieldofmilitary，routinginthefieldofnetworkcommunication，etc.Asaresult，theefficiencyoftheshortestpathalgorithminpracticalapplicationofproductdevelopmentstillneedtocontinuouslyimprove.ThisarticlewillbetotheshortestpathproblemisoneofthemostclassicalDijkstra（Dijkstra）algorithmisintroducedandtheoptimizationimprovement.Iwillimproveafterthisoptimizationalgorithmcalled：DJ_rayalgorithm，meaning：theDijkstraalgorithmtooptimizedivergentthinking.ThisarticlewillbetothetraditionalDijkstraalgorithmandtheoptimizationoftheimprovedDJ_rayalgorithm，inthethought，principle，method，datastructurearecompared，andexplainandanalysiscomparisonfromtimeandspacecomplexity.Atthesametime，inordertobetterdisplayDJ_rayalgorithmadvantagesinpracticalapplication，thetextwillbeDJ_rayalgorithminGIS，thetraintrafficnetworkrouteasacase，throughacombinationoftheoryandpracticeforeveryone.

Keywords：shortestpath；trafficroutes；Dijkstraalgorithm；DJ_rayalgorithm

1绪论

最短路径问题是图论中非常重要的最优化问题之一，也一直是计算机科学、交通工程学、地理信息系统（GIS）、运筹学等学科领域研究的热点。为了清晰的向大家展示其作用，以下我将通过火车最优路线选择的案例进行阐述Dijkstra算法。该算法是目前交通网络图在单源最短路径问题上运用最普遍、完善的算法之一，也是目前公认在非负权值，且所有的权大于等于零时，寻求最短路问题最好的算法，但是这样的方法依旧存在一些缺陷，如果不对这些缺陷进行完善改进而直接投入实际生产中，必将会造成不必要的损失。

本文将分为以下四个部分：第一部分概述Dijkstra算法在案例中实现的意义。第二部分介绍Dijkstra算法，并提出算法优化改进的方案—DJ_ray算法。第三部分描述DJ_ray算法的实现过程和复杂度分