導航過程中最短路徑的動態(tài)調(diào)整算法

趙忠孝，馮嫻

(1.福州外語外貿(mào)學院 信息系，福建 福州 350202; 2.福建工程學院 軟件學院，福建 福州 350003)

導航過程中最短路徑的動態(tài)調(diào)整算法

趙忠孝1，馮嫻2

(1.福州外語外貿(mào)學院 信息系，福建 福州 350202; 2.福建工程學院 軟件學院，福建 福州 350003)

在導航過程中，當最短路徑道路上有擁擠、堵塞或中斷的情況發(fā)生時，利用Dijkstra最短路徑算法中的最短路徑長度和前驅(qū)結(jié)點兩個輔助向量數(shù)據(jù)，可迅速在其鄰接結(jié)點中選擇一條新的最短路徑。實現(xiàn)了最短路徑的動態(tài)調(diào)整，從而可以盡快地到達目的地。

導航; 圖論; 最短路徑; Dijkstra

最短路徑問題是圖論中的一個經(jīng)典課題，在各種導航系統(tǒng)中有廣泛的應用。最短路徑算法有距離、時間和經(jīng)濟效益等多種判斷標準，一般僅以時間花費作為判斷最短路徑的標準。最短路徑算法分靜態(tài)最短路徑和動態(tài)最短路徑算法。Dijkstra等傳統(tǒng)的最短路徑算法屬靜態(tài)最短路徑算法，其研究已經(jīng)比較成熟，動態(tài)最短路徑算法成為近期研究的熱點。在動態(tài)最短路徑算法中，有限定搜索區(qū)域的算法[1]，也有限定搜索方向的A*算法[2-5]，其基本思路是縮小搜索的范圍，提高了搜索效率。這些算法都是在路徑參數(shù)動態(tài)變化的情形下重新搜索最短路徑，忽略了由靜態(tài)算法搜索最短路徑時所生成的相關數(shù)據(jù)?，F(xiàn)有的動態(tài)最短路徑的算法都是根據(jù)路徑中變化權值，重新搜索最短路徑，其時間花費均在O(N2)之上。實際上，在導航開始時已經(jīng)搜索到一條最短路徑，并有最短路徑長度和前驅(qū)結(jié)點兩個輔助向量的數(shù)據(jù)。在導航的過程中，只是在最短路徑上發(fā)生了擁擠、堵塞或中斷。此時，并不需要在整個路網(wǎng)中重新搜索，完全可以利用已有的數(shù)據(jù)，對部分路徑進行一些小范圍的調(diào)整，便可迅速選擇一條新的最短路徑。

1 相關概念

Dijkstra 最短路經(jīng)算法是計算帶權有向圖從源點V0到其他各點的最短路徑，按路徑長度的遞增次序，逐步產(chǎn)生 “貪心”(Greedy)的算法。為方便，本文僅以無向圖為例進行討論。實際上，交通線路等大多數(shù)是無向圖。對于有向圖，若某弧不存在，則可認為其對應的邊不存在即可。下面先介紹該最短路徑算法中用到的相關概念。

1.1 定義

設有向圖G=(V,E),給定結(jié)點v1,v2,…，vn∈V, 邊e1,e2,…，em∈E,用鄰接矩陣C表示有向圖G，權C[i][j]定義為：

其中，wij表示邊(vi,vj)上權值，∞表示一個計算機允許的、大大大于所有邊上權值的數(shù)。

1.2 相關的數(shù)據(jù)結(jié)構(gòu)

用C語言定義的數(shù)據(jù)結(jié)構(gòu)：

#define MaxVertexNum 100

∥*最大頂點數(shù)設為100

#define MAX 90 000.0

∥*設定最大權值為90 000.0

typedef char VertexType;∥*頂點類型設為字符型

typedef float EdgeType; ∥*邊的權值設為實型

typedef struct

{VertexType vexs[MaxVertexNum];∥*頂點表

EdgeType

edges[MaxVertexNum][MaxVertexNum]; ∥*鄰接矩陣，即邊表

int n,e; ∥*頂點數(shù)和邊數(shù)

}MGraph;

intP[N];

floatD[N];

MGraph *G。

(1)用鄰接矩陣來表示帶權無向圖(圖1)。

(2)輔助向量floatD[N]用來存儲源點到其余各結(jié)點的最短路徑長度。

(3)輔助向量floatP[N]用來存儲源點到其余各結(jié)點的最短路徑上前驅(qū)結(jié)點。

圖1有11個結(jié)點，圖中的數(shù)值表示其對應邊上的權值，其鄰接矩陣如圖2所示。

由Dijkstra最短路徑算法，能夠計算出從一個結(jié)點到其他結(jié)點的最短路徑。比如，從V0到其他結(jié)點的最短路徑。在圖3中，V0到各結(jié)點的實線路徑為最短路徑，虛線為原來邊。這樣，V0到V6的最短路徑為：V0→V2→V5→V6。V0到V10的最短路徑為：V0→V2→V5→V7→V10。由于是無向圖，從V10到V0的最短路徑應該是相反的一條路徑V10→V7→V5→V2→V0，其長度是一樣的。在這條路徑上，稱路徑上將要到達的結(jié)點為前驅(qū)結(jié)點，如V7是V10的前驅(qū)結(jié)點，V5是V7的前驅(qū)結(jié)點等。

圖1 有權無向圖Fig.1 Weighted undirected graph

圖2 鄰接矩陣

Fig.2 Adjacency matrix

圖3 最短路徑圖Fig.3 The shortest path graph

在Dijkstra算法結(jié)束時，各結(jié)點到V0最短路徑長度存儲在輔助向量D[N]中。具體數(shù)值如表1所示。

表1 各結(jié)點到V0的最短路徑值Tab.1 The shortest path value of each node to V0

各結(jié)點到V0的最短路徑上的前驅(qū)結(jié)點存儲在輔助向量P[N]中。具體數(shù)值如表2所示：

表2 各結(jié)點到V0的最短路徑的前驅(qū)結(jié)點

Tab.2 The precursor nodes of the shortest path of each node toV0

結(jié)點012345678910前驅(qū)00011255067

若現(xiàn)在從V10沿著最短路徑向V0行駛，當行使到V5時發(fā)現(xiàn)V5-V2的道路堵塞或中斷。此時，如何迅速地重新選擇一條新的最短路徑，就是一個迫切需要解決的問題。

2 算法思想

如果V5-V2之間的道路堵塞或中斷，則其對應邊上的權值就會增大。例如：w25=3變成w’25=7，其增值為4,用w=4來表示。這樣原來最短路徑值也隨之發(fā)生改變，改變后的值用D’[5]表示：

D’[5]=D[5]-w25+w’25=5-3+7=9

從V5到V0的最短路徑長度由5變成了9。這樣，原來的最短路徑可能已經(jīng)不是最短路徑了，需要重新計算來確定一條新的最短路徑。從V5出發(fā)到V0的最短路徑一定是經(jīng)過V5鄰接點的一條路徑，V5鄰接點有V2、V4、V6、V7、V8和V9。這些鄰接點到V0都是已經(jīng)有最短路徑，現(xiàn)只需要從V5經(jīng)過其鄰接點到V0的所有可能的最短路徑中選擇一條最短的路徑即可。也就是：

D’[5]=MIN{(D[i]+w5i) |Vi∈V5的鄰接結(jié)點}。

現(xiàn)可將V5的鄰接結(jié)點劃分為兩個集合，分別命名為S1和S2。其中S1的結(jié)點是其到V0的最短路徑不經(jīng)過V5的結(jié)點，如V2、V4、V8等結(jié)點。S2的結(jié)點是其到V0的最短路徑經(jīng)過V5的結(jié)點，如V6、V7等結(jié)點。對于S1中的結(jié)點，V5經(jīng)過各結(jié)點的最短路徑的值計算如下：

D[2]+w52=2+7=9,

D[4]+w54=6+2=8,

D[8]+w58=6+3=9,

其中最小的值為8,是經(jīng)過V4的一條路徑的值，用min1=8表示。但還不能確定min1=8就是最短路徑的值，還需要和S2中結(jié)點的最短路徑進行比較。由于S2中結(jié)點的最短路徑也走V5-V2這條邊，其原最短路徑的值自然也會增大，也需要重新確定一條最短路徑。對于Vi∈S2，如果D[i]+w5i的值已經(jīng)大于min1, 則可以排除在外。如：D[7]+w57=8+3=11,新的最短路徑值一定不會大于min1，可以排除經(jīng)過此結(jié)點為最短路徑經(jīng)過的結(jié)點。而對于V6來說，D[6]+w56=6+1=7,其值雖小于min1，但其原來最短路徑經(jīng)過V5，V6原來的最短路徑也可能已經(jīng)不是最短路徑了。其最短路徑的值也還不能直接確定，需要用相同的方法，也就是遞歸算法來確定V6最短路徑的值。如果V6鄰接點中仍有結(jié)點最短路徑經(jīng)過當前結(jié)點，仍需要繼續(xù)遞歸，直到?jīng)]有鄰接點的最短路徑經(jīng)過當前結(jié)點為止。

為不失一般性，設發(fā)生堵塞或中斷的結(jié)點為Vk，也就是要調(diào)整從Vk到V0的最短路徑。由于各結(jié)點最短路徑的前驅(qū)結(jié)點存儲在向量P[N]中，若P[i]=k,則鄰接點Vi到V0的最短路徑直接經(jīng)過結(jié)點k，否則沒有經(jīng)過。Vk鄰接點則是鄰接矩陣k行中對應值小于∞的那些結(jié)點。其算法形式化描述如下：

dynamicshort(MGraph *G,intk,floatw)

∥*G為帶權有向圖，k為當前結(jié)點，w為路徑的增值

{D[k]=D[k]+w; ∥* 修改當前結(jié)點到V0的路徑長度

min1=D[k];

i=0;

{ min1=min{D[i]+G->edges[k][i]|Vi∈s1}; ∥*s1為最短路徑不過Vk的結(jié)點集

}

i=0;

{ if(min1>D[i]+G->edges[k][i])

dynamicshort (G,i,w);

if(min1>D[i]+G->edges[k][i])

∥*判斷新路徑是否為最短路徑，若是則修改最小值，并記下當前結(jié)點。

{ min1=D[i]+G->edges[k][i];

p1=i++;

}

}

P[k]=p1; ∥*修改當前結(jié)點的前驅(qū)結(jié)點

D[k]=min1;∥*修改最短路徑長度

return;

}。

3 算法分析

由Dijkstra等單源最短路徑算法的結(jié)果，是生成以單源結(jié)點為根的一顆樹。各結(jié)點走向樹根的路徑就是其最短路徑。在前進方向上堵塞或中斷時，僅需要從其鄰接結(jié)點尋找最短路徑。一般情況下，道路的鄰接矩陣是一個稀疏矩陣，每個點的鄰接點的數(shù)量也十分有限，會大大小于網(wǎng)絡總的結(jié)點數(shù)。在鄰接點中，S1中的結(jié)點數(shù)N1一般應大于S2的結(jié)點數(shù)N2。對S1中的結(jié)點，只需要N1檢索。對于N2中的結(jié)點，若min1是已經(jīng)找到的最短路徑的值，對于原最短路徑大于該值的，不需要進一步再判定。只需要將那些原來的最短路徑值小于min1的結(jié)點遞歸調(diào)用本算法。且每遞歸一次，其最短路徑的值都在增加，若其值超過min1則終止。因最短路徑是一個樹型結(jié)構(gòu)，遞歸調(diào)用到葉結(jié)點將會終止。因此，遞歸調(diào)用的層次也是非常有限的。本文對有20個結(jié)點的網(wǎng)絡中的每個結(jié)點進行了最短路徑調(diào)整的測試。每次測試時，將結(jié)點與其前驅(qū)結(jié)點的邊值增加一個隨機值。使其原來的最短路徑發(fā)生了改變，統(tǒng)計了各結(jié)點搜索新的最短路徑其循環(huán)次數(shù)c1(在算法已有標示)和最短路徑值的修改次數(shù)c2(在算法已有標示)。各結(jié)點搜索次數(shù)的具體結(jié)果見表3。

表3 各結(jié)點搜索次數(shù)統(tǒng)計Tab.3 Each node search statistics

對這20個結(jié)點的網(wǎng)絡利用本算法，使改變的路徑調(diào)整到最短路徑只需要平均49.5次循環(huán)，對最短路徑的值進行了2.6次修改。其總的時間復雜度一般不會超過O(n)。若用Dijkstra最短路徑算法進行搜索，則需要760次循環(huán)，最短路徑的值也要進行76次修改運算。

4 結(jié)束語

在文獻[2]中，證明了動態(tài)網(wǎng)絡的最短路徑是一個NP完全問題，將動態(tài)問題化為若干個時間段，分段是穩(wěn)定的。每個穩(wěn)定區(qū)間都要解不等式組，迭代次數(shù)為k，k為子區(qū)間數(shù)。依次將每一個穩(wěn)定區(qū)間的解連接起來得到整體的解。其初始要調(diào)用Dijkstra算法，算法復雜度為O(n2)，各子區(qū)間算法的時間復雜度為O(mK)，K=max(n,k)。文獻[3]中算法的時間復雜度比Dijkstra算法僅快1～2倍。其他文獻所給出算法的復雜度都在O(n2)附近，本算法的時間復雜度遠遠低于已有的算法。在遇到堵塞或中斷事件后，可利用本算法迅速找到另一條到達目的地的最短路徑。

[1]汪曉潔,湯建國，李娟，等.基于可變權值的態(tài)最短路徑算法[J].新疆大學學報(自然科學版)，2015，32(3)：342-346.

[2]林瀾,閆春綱,蔣昌俊，等.動態(tài)網(wǎng)絡最短路問題的復雜性與近似算法[J].計算機學報,2007,30(4)：608-614.

[3]鄒亮,徐建閩,朱鈴湘.A_算法改進及其在動態(tài)最短路徑問題中的應用[J].深圳大學學報(理工版),2007，24(1)：32-35.

[4]周琳，陳發(fā)鋼.車載導航系統(tǒng)中動態(tài)最短路徑研究[J].牡丹江師范學院學報(自然科學版),2013(3):23-25.

[5]章昭輝.一種基于離散變權網(wǎng)絡的動態(tài)最短路徑快速算法[J].計算機科學,2010，37(4)：238-240.

[6]張一珂，劉鴻劍，朱志斌,等.基于車輛導航的一種改良動態(tài)最短路徑算法[J].科技廣場,2009(5)：26-28.

[7]任子輝，王堅.緊急事件的動態(tài)交通流模型及雙向動態(tài)最短路誘導算法[J].計算機應用,2008，28(11)：2955-2960.

[8]陳曉紅，王艷娟.改進的Dijkstra算法在動態(tài)路徑引導中的實現(xiàn)[J].科學技術與工程,2008，8(22)：6024-6027.

[9]田鵬飛，王劍英.動態(tài)最短路徑算法及其仿真 [J].計算機仿真,2007，24(6)：153-155.

[10]Huang A B, Wu B Q, Zhan F B. A shortest path algorithm with novel heuristics for dynamic transportation networks[J]. Intenational Journal of Geographical Information Science,2007(6)：625-644.

[11]Chabini I, Lan S. Adaptations of the A* algorithm for the computation of fastest in deterministic discrete time dynamic networks[J]. IEEE Transactions on Intelligent Transportation Systems,2002,3(1):60-74.

[12]SharmaY, Saini S C, Bhandhari M. Comparison of dijkstra shortest path algorithm with genetic algorithm for static and dynamic routing network[J]. International Journal of Electronics and Computer Science Engineering,2012,1(2):516-525.

(特約編輯：黃家瑜)

A dynamic alignment algorithm for the shortest path in the navigation process

Zhao Zhongxiao, Feng Xian

(1. Information Department, Fuzhou College of Internation Studies and Trade，F(xiàn)uzhou 350202，China;2. Software College, Fujian University of Technology, Fuzhou 350003, China)

The distance (length) of the shortest path and the data of two supplementary vectors of the previous nodes were adopted to quickly generate an alternative shortest path from adjacency nodes via Dijkstra algorithm. The dynamic alignment of the shortest path in navigation process was implemented to reach the destination in prompt moment.

navigation； graph theory； shortest path； Dijkstra

2016-06-27

趙忠孝(1948- )，男，山西聞喜人，教授,研究方向：算法設計與分析、數(shù)據(jù)庫設計。

10.3969/j.issn.1672-4348.2016.06.006

TP301

A

1672-4348(2016)06-0543-04