柳静

摘要：最短路径的分析与选取是测距过程的核心环节，在提高测距精度及降低测量成本方面发挥着重要的作用。提出一种基于Dijkstra算法的测距最短路径选取方法研究，深度剖析Dijkstra算法基本原理并给出相对应的伪码；基于最短路径上的某个顶点，识别出可能存在的多条最短路径；依据配对堆结构对测距时的多路径进行优先级队列操作，能够识别和选择出最佳测距路径。实验结果表明，提出的Dijkstra算法能够有效解决测距中的最短路径选取问题，并提高整体测距活动的精度与效率。

关键词： Dijkstra算法；测距；最短路径；配对堆结构

中图分类号： TP392 文献标识码： A 文章编号：1009-3044（2018）09-0041-03

测距过程中最佳路径的选取问题是测量领域的经典问题之一，识别出两个测量结点之间的最短路径[1]，不仅能够提高测量精度、降低测量误差，还能够大幅度地降低测量成本[2]。Dijkstra算法是研究最短路径选取的经典算法之一，在城市智能交通系统应用、物流运输、多点网络路由和电力测绘测量等领域均有应用[3-4]。研究测量、测绘过程中的最佳路径选择问题，可以将其转化为网络构图中的最短路径选取问题。因此，测量时的最短路径选择问题不能够单纯地理解为两点间的最短距离，而是要保证距离维度、时间维度及经济维度等方面均保证最优。Dijkstra算法是目前公认最佳的测距求解方法之一，但多点、多路径的综合识别问题，经典的Dijkstra算法[5-6]并未提及，故本文在研究经典Dijkstra算法的基础上，给出了具体的算法伪码，基于配对堆结构对多定点、多路径测距过程中的最佳路径识别问题进行研究，克服经典算法的不足，提高了整个算法的精度和可靠性。实验数据也验证了提出改进测距路径选取方面的有效性和实用性。

1 问题分析及算法描述

基于经典Dijkstra算法基本原理给出测距过程中改进算法的伪码，如下所示：

function for each v in G

dist v ：=in

previous[v]：=un

end for

dist v ：=[resource]：11

Q：=NODE

While Q is empty

U： remove Q from u： if dist [u]：=infinity

end if

break

for each of or u

alt：=dist [u]+dist between u and v

dist[v]：=

alt： =dist [v]

dist[v]：=alt

previous [v]：[u]

end： if

and while：=

依據改进Dijkstra算法，在测距时能够识别出同一顶点的多条最短路径，并从多条路径中选定出最为经济的路径。

2 基于Dijkstra算法多条测距最短路径识别

在基于Dijkstra算法进行空间顶点标号选择与测距最短路径的选取中，需要设定一种退出机制，即当[r≥0]且[Tr≠?]时，能够确保在第[k]步时识别出未通过的[Tr]集合。一般来说，有带权图[G]中的两个顶点之间不存在一种联通的关系，算法将会失效。而改进Dijkstra算法的伪码规则，将能够避免出现测距过程中失效情况的发生。如果空间的多个顶点，同时获得[p]标号，且[qi]标号相同，那么在带权图[G]中的所有点将会同时获得[p]标号。

从改进的Dijkstra算法中的伪码编码能够分析出，测距环节中的默认最短路径，一定为空间中某个顶点与其前置邻接点的连线。但从原点出发，到目标点的路径存在多条，每次获得标号的顶点位置也无法准确地获取，因此必须对标注顶点进行永久标注，避免在后续的路径选择中重复计算。为证明在测距的过程中，多个顶点和多条路径是客观存在的，设定一个有向带权图，如图1所示：

其余各顶点的路径距离变化图，如上图所示，可见测量路径的距离变化情况不尽相同。为求得多条路径的最短距离，需要基于改进Dijkstra算法进行带项权路径中各条测量路径距离的模拟运算，数据测量的过程中，多条最短路径是客观存在的，这是由于测量最短路径的初始顶点上存在多个前置的邻接点，经典算法无法解决如上的问题，可以基于配对堆结构的优先级队列算法，进行优先选择，识别出成本最低的最优路径。

3 基于配对堆结构的优先级队列操作与最佳路径选取

依据改进的Dijkstra算法中的伪码编码原则及测量最短路径运算数据，本文对Dijkstra算法进行了进一步的优化处理，引入新式的配对堆结构算法实现路径的最优排序和数据结构的性能优化。配对堆结构的主体构成是由一系列的配对堆节点有机组合构成，结构节点的主要功能是用于测量最优路径的选择与排序，配对堆结构的主要结构如下图所示：

如上图所示Dijkstra算法堆节点前置驱节点、子节点和兄弟节点构成。依据节点之间的依存关系，对不同层次的节点进行匹配。父节点、子节点和兄弟节点之间能够依据元素间的依存关系进行配对堆结构处理，按照最小值的配准原则进行匹配。由于Dijkstra算法可知，配准堆结构中堆节点的元素值小于子节点中的元素值；但有大于父节点中的元素值；而任一个堆节点中的数据值又小于兄节点中的元素值，兄节点之间的元素值没有大小之分。上述规则是由于堆节点的合并特性所决定的，基于上述的排列规则。就能够弥补经典Dijkstra算法无法选定同一顶点路径的不足，对这些待选路径进行可降级式的优先队列，从而选定出最佳的测量路径。

基于配对堆结构方法将这些已知的路径进行排序处理，还需要确定一种快速的访问路径。当访问到目标节点时，动态元素就能够生成与目标节点相对应的堆节点。这样操作就能够克服经典Dijkstra算法的不足，快速的筛选出最短、最经济的测距路径，而且能够提高整个路径识别过程中的速度与效率，目标节点与配对堆节点的对应关系如图3所示：

本文算法在经典Dijkstra算法的基础上，重新编写了伪码規则并构造配对堆节点，进行动态的路径选择与配置，从而能够在同一顶点的多条路径中选择出最优路径，降低运算的复杂程度和运算成本，提高了运算精度。

4 实验结果验证

将本文改进的Dijkstra算法与经典算法的运行时间进行对比，具体数据如表1所示：

表中数据显示，融入新的伪码规则和配对堆结构方法后，路径选择耗时大幅度降低：

从上述算法实验的数据来观测，本文算法在测量路径选择效率及误差率控制方面对比经典算法都具有明显的优势。

5 结束语

Dijkstra算法是测距的经典算法，但在具体的路径选择方面存在一定的不足。本文在研究经典算法的基础上，重新编制了伪码规则，并采用了配对堆结构算法对全部路径进行了排序处理，能够在较短的时间内，选定出测距过程中的最短路径，提高了算法的精度。

参考文献：

[1] 杜景林， 侯大俊. 基于Dijkstra算法的社交网络抽样生成[J]. 计算机应用， 2016， 36（6）：1506-1509.

[2] 王乙斐， 唐飞， 刘涤尘，等. 基于Dijkstra算法的最优解列断面快速搜索方法[J]. 电力自动化设备， 2015， 35（4）：126-131.

[3] 任鹏飞， 秦贵和， 董劲男，等. 具有交通规则约束的改进Dijkstra算法[J]. 计算机应用， 2015， 35（9）：2503-2507.

[4] 江渝， 叶泓炜， 张青松，等. 能源互联网中基于Dijkstra算法的分布式电能路由策略的实现[J]. 电网技术， 2017， 41（7）：2071-2078.

[5] 张怿宁， 王彩芝， 李京，等. 直流接地极线路单端行波故障测距算法[J]. 电力系统及其自动化学报， 2016， 28（4）：91-95.

[6] 王鹏， 张晓彤， 徐丽媛，等. 基于自适应时延估计的室内近场测距算法[J]. 计算机学报， 2017， 40（8）：1902-1917.