引言

路徑選擇問題是解決車載導航系統(tǒng)中的核心問題，歸根結底是最短路徑問題?，F(xiàn)有的最短路徑算法有很多，如迪杰斯特拉（Dijkstra）、弗洛伊德（Floyd）及其改進算法、盲目捜索法，啟發(fā)式A*算法、人工神經(jīng)網(wǎng)絡、遺傳算法、蟻群算法等［%而這其中又是以迪杰斯特拉及其改進算法最經(jīng)典,是研究得最多的一種算法，并取得了一定的成果，然而，對這些成果進行分析發(fā)現(xiàn)，研究的這些算法都是靜態(tài)的，以圖論為基礎的方法，并沒有考慮到障礙物的影響。因此，本文主要對有障礙物影響的情況下的最短路徑算法進行研究，并利用MapX控件實現(xiàn)了最短路徑的算法，在車載導航中取得了較好的應用。

1Dikjsrta算法存在的問題

Dikjsrta算法是由荷蘭數(shù)學家E.W.Dikjsrta于1959年提出單源最短路算法，是目前求解最短路問題的理論上最完備、應用最廣的經(jīng)典算法，它可完成從指定圖中所有其他節(jié)點的最短路徑，它是主要路徑長度遞增產(chǎn)生最短路徑算法，此算法在諸多教材中均有闡述。從所介紹的算法不難看出存在兩點不足:①只考慮靜態(tài)的最短路徑，沒有及時反映出存在障礙物（如交通阻塞、修路等情況）下的最短路徑；②圖的存儲結構中存在著大量的8,浪費了大量的存儲空間。因此本文從以上兩個方面加以改進。

2Dikjsrta算法的改進

2.1有障礙物存在時的改進Dikjsrta算法

通過對各類公交流量的分析和研究，可將城市道路障礙物分為阻塞和繁忙兩種狀態(tài)，如修路行不通為阻塞狀態(tài)、上下班堵車為繁忙狀態(tài)，在這兩種狀態(tài)情況下，必須另錄一條最短路徑以獲得時間最短。將障礙物反映到圖上，則存在兩種情況：一是正好在相應節(jié)點上（如圖1節(jié)點2上），貝嶼其相連的節(jié)點上各邊權值變?yōu)?；二是在相應的某一條邊上（如節(jié)點1-3）之間，貝懼相鄰接的鄰接矩陣變?yōu)?。其改進算法如下：

建立鄰接矩陣A[v,][vJ]?若v障礙物正好處于圖的節(jié)點，則此節(jié)點是車載不允許經(jīng)過的節(jié)點，A[:][Vj]=8,亦矩陣中V所在的列的元素均取8。若障礙物正好位于兩節(jié)點之前,即此段路程不通必須加以回避，設e,j=(v?Vj)為必須回避的邊,則A[v；][vj]=8。

初始化。S={vs)(vseV),dist[vi]=A[vs][vi],path[Vj]={vs},vieV,i=1,2,…，n。

選擇Vk，使得dist[Vk]=min(dist[v』VieV-S),S=SU{Vk}。Vk為目前求得的下一條從Vs出發(fā)的最短路徑的終點。如果Vk夭Vt，轉向(4),否則結束,dist[Vt]即為回避的點、邊、路徑障礙下從Vs到頂點vt的最短路徑。

修改從v出發(fā)到集合V-S任一頂點Vi的最短路徑長度。設V為路徑path[Vk]倒數(shù)第二個節(jié)點。若dist[Vk]+A[Vk][Vi]<dist[Vi],則dist[i]=dist[Vk]+A[Vk][Vi],path[Vi]=path[Vk]U{財，轉向(3)。

圖1所示是一種有路障的加權圖G',圖1中，假設節(jié)點2號有路障，另外1-3號節(jié)點的路段正在修路不能通行，其存儲的鄰接矩陣如圖2所示。

圖2圖G'的鄰接矩陣

2.2存儲結構的改進

無論是有無障礙物的Dikjsrta算法，采用矩陣來存儲點與點間的拓撲關系，行數(shù)和列數(shù)相同，矩陣中i行J列的值對應著點i和點J之間的權值，起點和終點為同一點時權值用0表示，兩點之間沒有直接通路時權值用8表示。矩陣中含有大量的0和8,增加了無效循環(huán)次數(shù)，在存儲上也占用了大量的空間，浪費了大量的空間。為提高內(nèi)存的利用率，本文采用的鄰接表存儲如圖3所示。

用鏈表數(shù)組MGrpah表示存儲矩陣G時，可將其每一行用一個單鏈表來表示，鏈表中只有非8元素，每個節(jié)點有兩個元素，一個為所在的列值，一為點的權值。其偽代碼如下:

Typedfstruct

{Intr,v；

Mnode*next；

}Mnode；

ClassMGraph{

Public:

Mnode*first,*current；

Mgraph(){current=null；first=current；}

Voidsetfirst(Mnode*p){first=p；current=first；}

Mnode*GotoFirst(){if(first){current=first；returncurrent；}

Elsereturnnull；}

VoidAdd(Mnode*p){current->next=p；current=p；}

Mnode*Next(){if(current->next){current=current->next；returncurrent；}

ElsereturnNULL；}

}

然后可用一維數(shù)組D來存儲各頂點到源點的最短距離,并用一維數(shù)組P來存儲前驅(qū)點，再用一個輔助雙向鏈表來存儲正在參與比較的節(jié)點(使用雙向鏈表的目的是在刪除節(jié)點時降低時間復雜度)。其代碼如下：

Typedefstruct{intr；Node*next,*prev；}chinaNode；

Classpath{

public:

chainNode*first,*current；

intn；

path(){n=0；current=null；first=null；}

voidsetfirst(chainnode*p){first=p；current=first；n=1；}

voidAddTail(chainNode*p){current->next=p；p->prev=current；current=p；n++}

intdelete(chainNode*p)；

chainNode*Next(){if(current->next){current=current->next；

returncurrent；}elsereturnnull；}

boolIsEmpty(){returnn==0；}

}

2.3改進算法的實現(xiàn)步驟

改進算法的實現(xiàn)步驟如下：

將與V。直接相連的節(jié)點的D[vJ初始化為其權值,其余的置為機器所允許的最大值。

將與V。直接相連的頂點加入到鏈表Path中。

在Path中找到權值最小的節(jié)點w,并在Path中刪除此頂點，如果剩余節(jié)點數(shù)為。則結束。

修改最短路徑：在G里與w直接相連的其余各節(jié)點Vj的權值中比較D[Vj]與D[w]+s(w,vD的大小，如果D[vJ小于D[w]+s(w,Vj),并且如果D[Vj]為8,則將Vj加入到Path中，然后將P[vJ的前驅(qū)設置為w,并修改最短路徑D[vJ=D[w]+s(w,V)。重復步驟(4)。

根據(jù)以上思路，利用MapX控件，結合可視化編程語言,對武漢市地圖矢量化，去除多余的結點，構建拓撲關系，結合改進的算法，進行編程，其實現(xiàn)的界面如圖4所示。

3結語

本文在研究現(xiàn)有的Dikjsrta算法的基礎上，討論了有障礙物存在的Dikjsrta的算法，并對其存儲結構進行了一點小的改進，給出了具體的實現(xiàn)過程，提高了存儲效率。存在的不足是沒有對時間與空間復雜度進行量化，另外，對其搜索方法

也沒有加以改進，這將是下一步努力改進的方向。

圖4障礙特存在的最短路徑展示圖

20211116_6193be3cc09ae__障礙物存在的最短路徑算法及其在車載導航中的應用