柳靜

摘要：最短路徑的分析與選取是測距過程的核心環(huán)節(jié)，在提高測距精度及降低測量成本方面發(fā)揮著重要的作用。提出一種基于Dijkstra算法的測距最短路徑選取方法研究，深度剖析Dijkstra算法基本原理并給出相對(duì)應(yīng)的偽碼；基于最短路徑上的某個(gè)頂點(diǎn)，識(shí)別出可能存在的多條最短路徑；依據(jù)配對(duì)堆結(jié)構(gòu)對(duì)測距時(shí)的多路徑進(jìn)行優(yōu)先級(jí)隊(duì)列操作，能夠識(shí)別和選擇出最佳測距路徑。實(shí)驗(yàn)結(jié)果表明，提出的Dijkstra算法能夠有效解決測距中的最短路徑選取問題，并提高整體測距活動(dòng)的精度與效率。

關(guān)鍵詞： Dijkstra算法；測距；最短路徑；配對(duì)堆結(jié)構(gòu)

中圖分類號(hào)： TP392 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)：1009-3044（2018）09-0041-03

測距過程中最佳路徑的選取問題是測量領(lǐng)域的經(jīng)典問題之一，識(shí)別出兩個(gè)測量結(jié)點(diǎn)之間的最短路徑[1]，不僅能夠提高測量精度、降低測量誤差，還能夠大幅度地降低測量成本[2]。Dijkstra算法是研究最短路徑選取的經(jīng)典算法之一，在城市智能交通系統(tǒng)應(yīng)用、物流運(yùn)輸、多點(diǎn)網(wǎng)絡(luò)路由和電力測繪測量等領(lǐng)域均有應(yīng)用[3-4]。研究測量、測繪過程中的最佳路徑選擇問題，可以將其轉(zhuǎn)化為網(wǎng)絡(luò)構(gòu)圖中的最短路徑選取問題。因此，測量時(shí)的最短路徑選擇問題不能夠單純地理解為兩點(diǎn)間的最短距離，而是要保證距離維度、時(shí)間維度及經(jīng)濟(jì)維度等方面均保證最優(yōu)。Dijkstra算法是目前公認(rèn)最佳的測距求解方法之一，但多點(diǎn)、多路徑的綜合識(shí)別問題，經(jīng)典的Dijkstra算法[5-6]并未提及，故本文在研究經(jīng)典Dijkstra算法的基礎(chǔ)上，給出了具體的算法偽碼，基于配對(duì)堆結(jié)構(gòu)對(duì)多定點(diǎn)、多路徑測距過程中的最佳路徑識(shí)別問題進(jìn)行研究，克服經(jīng)典算法的不足，提高了整個(gè)算法的精度和可靠性。實(shí)驗(yàn)數(shù)據(jù)也驗(yàn)證了提出改進(jìn)測距路徑選取方面的有效性和實(shí)用性。

1 問題分析及算法描述

基于經(jīng)典Dijkstra算法基本原理給出測距過程中改進(jìn)算法的偽碼，如下所示：

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：=

依據(jù)改進(jìn)Dijkstra算法，在測距時(shí)能夠識(shí)別出同一頂點(diǎn)的多條最短路徑，并從多條路徑中選定出最為經(jīng)濟(jì)的路徑。

2 基于Dijkstra算法多條測距最短路徑識(shí)別

在基于Dijkstra算法進(jìn)行空間頂點(diǎn)標(biāo)號(hào)選擇與測距最短路徑的選取中，需要設(shè)定一種退出機(jī)制，即當(dāng)[r≥0]且[Tr≠?]時(shí)，能夠確保在第[k]步時(shí)識(shí)別出未通過的[Tr]集合。一般來說，有帶權(quán)圖[G]中的兩個(gè)頂點(diǎn)之間不存在一種聯(lián)通的關(guān)系，算法將會(huì)失效。而改進(jìn)Dijkstra算法的偽碼規(guī)則，將能夠避免出現(xiàn)測距過程中失效情況的發(fā)生。如果空間的多個(gè)頂點(diǎn)，同時(shí)獲得[p]標(biāo)號(hào)，且[qi]標(biāo)號(hào)相同，那么在帶權(quán)圖[G]中的所有點(diǎn)將會(huì)同時(shí)獲得[p]標(biāo)號(hào)。

從改進(jìn)的Dijkstra算法中的偽碼編碼能夠分析出，測距環(huán)節(jié)中的默認(rèn)最短路徑，一定為空間中某個(gè)頂點(diǎn)與其前置鄰接點(diǎn)的連線。但從原點(diǎn)出發(fā)，到目標(biāo)點(diǎn)的路徑存在多條，每次獲得標(biāo)號(hào)的頂點(diǎn)位置也無法準(zhǔn)確地獲取，因此必須對(duì)標(biāo)注頂點(diǎn)進(jìn)行永久標(biāo)注，避免在后續(xù)的路徑選擇中重復(fù)計(jì)算。為證明在測距的過程中，多個(gè)頂點(diǎn)和多條路徑是客觀存在的，設(shè)定一個(gè)有向帶權(quán)圖，如圖1所示：

其余各頂點(diǎn)的路徑距離變化圖，如上圖所示，可見測量路徑的距離變化情況不盡相同。為求得多條路徑的最短距離，需要基于改進(jìn)Dijkstra算法進(jìn)行帶項(xiàng)權(quán)路徑中各條測量路徑距離的模擬運(yùn)算，數(shù)據(jù)測量的過程中，多條最短路徑是客觀存在的，這是由于測量最短路徑的初始頂點(diǎn)上存在多個(gè)前置的鄰接點(diǎn)，經(jīng)典算法無法解決如上的問題，可以基于配對(duì)堆結(jié)構(gòu)的優(yōu)先級(jí)隊(duì)列算法，進(jìn)行優(yōu)先選擇，識(shí)別出成本最低的最優(yōu)路徑。

3 基于配對(duì)堆結(jié)構(gòu)的優(yōu)先級(jí)隊(duì)列操作與最佳路徑選取

依據(jù)改進(jìn)的Dijkstra算法中的偽碼編碼原則及測量最短路徑運(yùn)算數(shù)據(jù)，本文對(duì)Dijkstra算法進(jìn)行了進(jìn)一步的優(yōu)化處理，引入新式的配對(duì)堆結(jié)構(gòu)算法實(shí)現(xiàn)路徑的最優(yōu)排序和數(shù)據(jù)結(jié)構(gòu)的性能優(yōu)化。配對(duì)堆結(jié)構(gòu)的主體構(gòu)成是由一系列的配對(duì)堆節(jié)點(diǎn)有機(jī)組合構(gòu)成，結(jié)構(gòu)節(jié)點(diǎn)的主要功能是用于測量最優(yōu)路徑的選擇與排序，配對(duì)堆結(jié)構(gòu)的主要結(jié)構(gòu)如下圖所示：

如上圖所示Dijkstra算法堆節(jié)點(diǎn)前置驅(qū)節(jié)點(diǎn)、子節(jié)點(diǎn)和兄弟節(jié)點(diǎn)構(gòu)成。依據(jù)節(jié)點(diǎn)之間的依存關(guān)系，對(duì)不同層次的節(jié)點(diǎn)進(jìn)行匹配。父節(jié)點(diǎn)、子節(jié)點(diǎn)和兄弟節(jié)點(diǎn)之間能夠依據(jù)元素間的依存關(guān)系進(jìn)行配對(duì)堆結(jié)構(gòu)處理，按照最小值的配準(zhǔn)原則進(jìn)行匹配。由于Dijkstra算法可知，配準(zhǔn)堆結(jié)構(gòu)中堆節(jié)點(diǎn)的元素值小于子節(jié)點(diǎn)中的元素值；但有大于父節(jié)點(diǎn)中的元素值；而任一個(gè)堆節(jié)點(diǎn)中的數(shù)據(jù)值又小于兄節(jié)點(diǎn)中的元素值，兄節(jié)點(diǎn)之間的元素值沒有大小之分。上述規(guī)則是由于堆節(jié)點(diǎn)的合并特性所決定的，基于上述的排列規(guī)則。就能夠彌補(bǔ)經(jīng)典Dijkstra算法無法選定同一頂點(diǎn)路徑的不足，對(duì)這些待選路徑進(jìn)行可降級(jí)式的優(yōu)先隊(duì)列，從而選定出最佳的測量路徑。

基于配對(duì)堆結(jié)構(gòu)方法將這些已知的路徑進(jìn)行排序處理，還需要確定一種快速的訪問路徑。當(dāng)訪問到目標(biāo)節(jié)點(diǎn)時(shí)，動(dòng)態(tài)元素就能夠生成與目標(biāo)節(jié)點(diǎn)相對(duì)應(yīng)的堆節(jié)點(diǎn)。這樣操作就能夠克服經(jīng)典Dijkstra算法的不足，快速的篩選出最短、最經(jīng)濟(jì)的測距路徑，而且能夠提高整個(gè)路徑識(shí)別過程中的速度與效率，目標(biāo)節(jié)點(diǎn)與配對(duì)堆節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系如圖3所示：

本文算法在經(jīng)典Dijkstra算法的基礎(chǔ)上，重新編寫了偽碼規(guī)則并構(gòu)造配對(duì)堆節(jié)點(diǎn)，進(jìn)行動(dòng)態(tài)的路徑選擇與配置，從而能夠在同一頂點(diǎn)的多條路徑中選擇出最優(yōu)路徑，降低運(yùn)算的復(fù)雜程度和運(yùn)算成本，提高了運(yùn)算精度。

4 實(shí)驗(yàn)結(jié)果驗(yàn)證

將本文改進(jìn)的Dijkstra算法與經(jīng)典算法的運(yùn)行時(shí)間進(jìn)行對(duì)比，具體數(shù)據(jù)如表1所示：

表中數(shù)據(jù)顯示，融入新的偽碼規(guī)則和配對(duì)堆結(jié)構(gòu)方法后，路徑選擇耗時(shí)大幅度降低：

從上述算法實(shí)驗(yàn)的數(shù)據(jù)來觀測，本文算法在測量路徑選擇效率及誤差率控制方面對(duì)比經(jīng)典算法都具有明顯的優(yōu)勢。

5 結(jié)束語

Dijkstra算法是測距的經(jīng)典算法，但在具體的路徑選擇方面存在一定的不足。本文在研究經(jīng)典算法的基礎(chǔ)上，重新編制了偽碼規(guī)則，并采用了配對(duì)堆結(jié)構(gòu)算法對(duì)全部路徑進(jìn)行了排序處理，能夠在較短的時(shí)間內(nèi)，選定出測距過程中的最短路徑，提高了算法的精度。

參考文獻(xiàn)：

[1] 杜景林， 侯大俊. 基于Dijkstra算法的社交網(wǎng)絡(luò)抽樣生成[J]. 計(jì)算機(jī)應(yīng)用， 2016， 36（6）：1506-1509.

[2] 王乙斐， 唐飛， 劉滌塵，等. 基于Dijkstra算法的最優(yōu)解列斷面快速搜索方法[J]. 電力自動(dòng)化設(shè)備， 2015， 35（4）：126-131.

[3] 任鵬飛， 秦貴和， 董勁男，等. 具有交通規(guī)則約束的改進(jìn)Dijkstra算法[J]. 計(jì)算機(jī)應(yīng)用， 2015， 35（9）：2503-2507.

[4] 江渝， 葉泓煒， 張青松，等. 能源互聯(lián)網(wǎng)中基于Dijkstra算法的分布式電能路由策略的實(shí)現(xiàn)[J]. 電網(wǎng)技術(shù)， 2017， 41（7）：2071-2078.

[5] 張懌寧， 王彩芝， 李京，等. 直流接地極線路單端行波故障測距算法[J]. 電力系統(tǒng)及其自動(dòng)化學(xué)報(bào)， 2016， 28（4）：91-95.

[6] 王鵬， 張曉彤， 徐麗媛，等. 基于自適應(yīng)時(shí)延估計(jì)的室內(nèi)近場測距算法[J]. 計(jì)算機(jī)學(xué)報(bào)， 2017， 40（8）：1902-1917.