趙忠孝，馮嫻

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

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

趙忠孝1，馮嫻2

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

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

導(dǎo)航; 圖論; 最短路徑; Dijkstra

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

1 相關(guān)概念

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

1.1 定義

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

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

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

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

#define MaxVertexNum 100

∥*最大頂點(diǎn)數(shù)設(shè)為100

#define MAX 90 000.0

∥*設(shè)定最大權(quán)值為90 000.0

typedef char VertexType;∥*頂點(diǎn)類型設(shè)為字符型

typedef float EdgeType; ∥*邊的權(quán)值設(shè)為實(shí)型

typedef struct

{VertexType vexs[MaxVertexNum];∥*頂點(diǎn)表

EdgeType

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

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

}MGraph;

intP[N];

floatD[N];

MGraph *G。

(1)用鄰接矩陣來(lái)表示帶權(quán)無(wú)向圖(圖1)。

(2)輔助向量floatD[N]用來(lái)存儲(chǔ)源點(diǎn)到其余各結(jié)點(diǎn)的最短路徑長(zhǎng)度。

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

圖1有11個(gè)結(jié)點(diǎn)，圖中的數(shù)值表示其對(duì)應(yīng)邊上的權(quán)值，其鄰接矩陣如圖2所示。

由Dijkstra最短路徑算法，能夠計(jì)算出從一個(gè)結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短路徑。比如，從V0到其他結(jié)點(diǎn)的最短路徑。在圖3中，V0到各結(jié)點(diǎn)的實(shí)線路徑為最短路徑，虛線為原來(lái)邊。這樣，V0到V6的最短路徑為：V0→V2→V5→V6。V0到V10的最短路徑為：V0→V2→V5→V7→V10。由于是無(wú)向圖，從V10到V0的最短路徑應(yīng)該是相反的一條路徑V10→V7→V5→V2→V0，其長(zhǎng)度是一樣的。在這條路徑上，稱路徑上將要到達(dá)的結(jié)點(diǎn)為前驅(qū)結(jié)點(diǎn)，如V7是V10的前驅(qū)結(jié)點(diǎn)，V5是V7的前驅(qū)結(jié)點(diǎn)等。

圖1 有權(quán)無(wú)向圖Fig.1 Weighted undirected graph

圖2 鄰接矩陣

Fig.2 Adjacency matrix

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

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

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

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

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

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

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

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

2 算法思想

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

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

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

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

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

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

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

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

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

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

dynamicshort(MGraph *G,intk,floatw)

∥*G為帶權(quán)有向圖，k為當(dāng)前結(jié)點(diǎn)，w為路徑的增值

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

min1=D[k];

i=0;

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

}

i=0;

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

dynamicshort (G,i,w);

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

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

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

p1=i++;

}

}

P[k]=p1; ∥*修改當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)

D[k]=min1;∥*修改最短路徑長(zhǎng)度

return;

}。

3 算法分析

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

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

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

4 結(jié)束語(yǔ)

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

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

[2]林瀾,閆春綱,蔣昌俊，等.動(dòng)態(tài)網(wǎng)絡(luò)最短路問(wèn)題的復(fù)雜性與近似算法[J].計(jì)算機(jī)學(xué)報(bào),2007,30(4)：608-614.

[3]鄒亮,徐建閩,朱鈴湘.A_算法改進(jìn)及其在動(dòng)態(tài)最短路徑問(wèn)題中的應(yīng)用[J].深圳大學(xué)學(xué)報(bào)(理工版),2007，24(1)：32-35.

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

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

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

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

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

[9]田鵬飛，王劍英.動(dòng)態(tài)最短路徑算法及其仿真 [J].計(jì)算機(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ì)與分析、數(shù)據(jù)庫(kù)設(shè)計(jì)。

10.3969/j.issn.1672-4348.2016.06.006

TP301

A

1672-4348(2016)06-0543-04