李卫民-彭认灿=基于动态限制搜索区域的dijkstra优化算法研究

《李卫民-彭认灿=基于动态限制搜索区域的dijkstra优化算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于动态限制搜索区域的Dijkstra优化算法研究李卫民，彭认灿，陈惠荣（海军大连舰艇学院海测工程系，辽宁大连116018）摘要:本文在比较两种Dijkstra优化算法的基础上，提出了一种动态限制搜索区域的优化算法。它是根据实际道路网络的空间分布特性，动态限制搜索区域，以降低算法的搜索规模、时间复杂度和空间复杂度，提高算法的运算效率。实验证明，对于实际城市道路网络结构相对比较规则的最短路径规划，此算法具有更高的效率。关键词:Dijkstra优化算法；最短路径；动态限制搜索区域；道路网络StudyofAnOptimizedDijkstraAlgorithmBas

2、edonDynamicRestrictedSearchingAreaLiwei-min,Pengren-can,Chenhui-rong(DepartmentofHydrographyandCartography,DalianNavalAcademy,Dalian,Liaoning,116018)Abstract:Anoptimizedalgorithmwithinadynamicrestrictedsearchingareahasbeenproposedonthebasisofthecomparisonbetweentwokindsofoptimizedal

3、gorithmsofDijkstra.Inordertoreducethesearchingsize，thetimecomplexityandspatialcomplexity，enhancetheefficiency，thisalgorithmtakesthemeasureofrestrictingthesearchingareaaccordingtothespatialdistributionfeatureoftherealroadnetworkdynamically.Theexperimentindicatesthealgorithmenhancesth

4、eefficiencyoftheshortest-routeplanninginthecitywhichhasarelativelyregularrealroadnetworkgreatly.Keywords:optimizedalgorithmofDijkstra；shortestroute；dynamicrestrictedsearchingarea；roadnetwork在GIS中，网络分析是其赖以生存的基础，它在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计都有极其广泛的应用，而其最基本、最关键的问题是最短路径问题。由于最短路径问

5、题在实际中常用于汽车导航系统以及各种应急系统，这些系统对实时性的要求较高，即对于一个给定了起始点和目标点的特定路径规划问题，要在尽可能短的时间内给出规划后的路径。最短路径算法设计与实现的基础是具有拓扑结构的道路网络。目前世面上流行的各种最短路径算法中，核心思想都只有一个，即Dijkstra算法。该算法是目前所有系统解决最短路径问题采取的理论基础。为了能更清楚地阐述本文的优化算法，首先对Dijkstra一般算法进行简单说明。1、Dijkstra一般算法1.1算法的主要思想基本思路可描述为：将网络结点分成3部分：未标记结点、临时标记结点和永久标记点。网络中所有结点

6、从首先初始化为未标记结点，在搜索过程中和最短路径中的结点相连通的结点为临时标记结点，每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，直至找到目标结点或者所有的结点都成为永久标记结点来结束算法。在此主要讨论在一个赋权的简单连通无向图中，求一结点(称为源点)到其他结点的最短路径的长度，通常称它为单源问题。下面介绍1959年E.W.Dijkstra提出的单源问题的算法。其要点如下：（1）把分成两个子集和，初始时，；（2）对中每一元素计算，(表示从到的不包含中其他结点的最短路径的长度)，根据值找出中距最短的结点，写出到的最短路径的长度；（3）

7、置为，置为，若，则停止，否则再重复（2）。1.2存在的不足近年来，由于图论与数据结构的有效结合，使得各种新的优化Dijkstra算法不断涌现。但由于这些算法主要诞生于计算机科学及运筹学领域，大多数算法均存在一个问题：在设计过程中只考虑了抽象网络的拓扑特性，力求通过各种新型的计算机数据结构和运筹学方法，从理论上减少算法的时间、复杂度而忽略了具体网络可能具有的空间分布特性。而要利用于GIS网络分析中，又不能不考虑具体应用网络中的相关空间分布特性，所以必须解决这个问题。另一方面，在Dijkstra一般算法中，临时标记结点无序地存储在无序表中，这无疑成为Dijkstr

8、a算法的瓶颈。因为Dijkstra算法