易文静　田俊峰

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

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

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）23-0166-03

Abstract： Research and application of the shortest path algorithm plays an important role in every field， such as the optimal route in the field of transportation， travel route in the field of military， routing in the field of network communication， etc.As a result， the efficiency of the shortest path algorithm in practical application of product development still need to continuously improve.This article will be to the shortest path problem is one of the most classical Dijkstra （Dijkstra） algorithm is introduced and the optimization improvement.I will improve after this optimization algorithm called： DJ_ray algorithm ，meaning： the Dijkstra algorithm to optimize divergent thinking.This article will be to the traditional Dijkstra algorithm and the optimization of the improved DJ_ray algorithm， in the thought， principle， method， data structure are compared， and explain and analysis comparison from time and space complexity.At the same time， in order to better display DJ_ray algorithm advantages in practical application， the text will be DJ_ray algorithm in GIS， the train traffic network route as a case， through a combination of theory and practice for everyone.

Key words： shortest path； traffic routes； Dijkstra algorithm； DJ_ray algorithm

1 绪论

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

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