基于移動(dòng)定位信息的最短路徑搜索算法

摘要:該文利用改進(jìn)的Dijkstra算法求出車(chē)輛行駛的最短路徑，并根據(jù)道路限定的車(chē)速，交通異常信息等對(duì)所求的最短路徑進(jìn)行分析，最終得到所用時(shí)間和距離最短的最短路徑。

關(guān)鍵詞:Dijkstra算法;最短路徑;交通異常信息

中圖分類(lèi)號(hào):TP31文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)32-9030-02

Based on the Mobile Pitch Information of the Algorithm for Shortest-path Searching

HU Ming， ZHAO Wan-ting

(Changchun University of Technology， Department of Computer Science and engineering， Changchun 130000， China)

Abstract: Make use of Dijkstra work out the shortest-path of the car run， and base the rate of the road limit， traffic exception information to analyses the shortest-path， at the end， find the shortest-path which use the least time and the shortest path.

Key words: dijkstra arithmetic; shortest-path; traffic exception information

隨著智能交通的發(fā)展和手機(jī)定位技術(shù)的不斷改進(jìn)，利用GPS/GSM網(wǎng)絡(luò)定位技術(shù)，可以對(duì)移動(dòng)目標(biāo)的運(yùn)動(dòng)軌跡及其速度、運(yùn)動(dòng)方向等參數(shù)進(jìn)行監(jiān)控和查詢(xún)，同時(shí)，根據(jù)所得到的車(chē)輛信息，可以搜索出車(chē)輛運(yùn)行的最短路徑，為出行者提供最便捷的到達(dá)目的的路徑，提高交通質(zhì)量。如何能在最短時(shí)間找出車(chē)輛行駛的最短路徑，如何能避免最短路徑中出現(xiàn)交通異常信息，這些問(wèn)題已經(jīng)成為當(dāng)下最需要解決的交通問(wèn)題[3]。交通信息系統(tǒng)中的最短路徑查詢(xún)，具有一定的實(shí)時(shí)性，同時(shí)要求查詢(xún)的最短路徑在時(shí)間上、路徑上都是最短的。

目前，經(jīng)典的最短路徑算法為Dijkstra算法，他提出了一個(gè)按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑的算法，但是，該算法是計(jì)算單點(diǎn)和多點(diǎn)之間的最短路徑，對(duì)于交通中點(diǎn)對(duì)點(diǎn)的最短路徑，該算法執(zhí)行了太多的無(wú)用操作，影響了計(jì)算的速度。

因此，在該算法的基礎(chǔ)上，調(diào)整點(diǎn)集，避免遍歷無(wú)用的點(diǎn)[5]，并根據(jù)當(dāng)前的交通信息對(duì)得到的最短路徑進(jìn)行分析，判斷所得的最短路徑中是否有交通異常路徑，如果有，再次調(diào)整點(diǎn)集及路徑集，重新計(jì)算最短路徑，并根據(jù)道路限定的車(chē)速判斷行駛時(shí)間，最后根據(jù)時(shí)間條件和路徑條件選擇適當(dāng)?shù)淖疃搪窂健?/p>

1 Dijkstra算法

Dijkstra算法的基本思想是:設(shè)置一個(gè)集合S存放已經(jīng)找到最短路徑的頂點(diǎn)，S的初始狀態(tài)只包含源點(diǎn)v，對(duì)vi<

Dijkstra算法的偽代碼描述如下:

1) 初始化數(shù)組dist、path和s;

2) while(s中的元素個(gè)數(shù)

i)在dist[n]中求最小值，其下標(biāo)為k(則vk 為正在生成的終點(diǎn));

ii) 輸出dist[j]和path[j];

iii) 修改數(shù)組dist和path;

iv) 將頂點(diǎn)vk 添加到數(shù)組s中;

對(duì)于算法中的數(shù)組及存儲(chǔ)結(jié)構(gòu)的設(shè)定見(jiàn)文獻(xiàn)[1]

2 改進(jìn)后的Dijkstra算法

2.1 算法分析

由于本文計(jì)算的是城市道路中的交通網(wǎng)絡(luò)，因此在最短路徑計(jì)算中的圖應(yīng)改為一個(gè)非有向的帶權(quán)圖，同時(shí)，路網(wǎng)表示的空間復(fù)雜度為O(an+bm)，其中a，b為常數(shù)，分別和路口、路段的信息量有關(guān)。

Dijkstra算法中計(jì)算一個(gè)點(diǎn)到其他點(diǎn)的最短路徑共需兩次循環(huán)，時(shí)間復(fù)雜度為O(n2)，這里由于需計(jì)算每一對(duì)頂點(diǎn)間的最短路徑，故需以每個(gè)頂點(diǎn)為原點(diǎn)，執(zhí)行算法n次，總的執(zhí)行時(shí)間復(fù)雜度為O(n3)。

2.2 基本定義

1) 對(duì)于圖G=(V， E， w)，設(shè)Vi={Vi∈V}是對(duì)圖G的一個(gè)劃分，當(dāng)且僅當(dāng):?坌Vα，Vβ∈Vi，其中Vα≠Vβ，即Vα∩Vβ=;

2) 對(duì)圖G=(V， E， w)，Vi={Vλ}是其上∩的一個(gè)劃分，?坌Va，Vb∈Vi稱(chēng)E的子集Ei(Va，Vb)為塊Va到塊Vb的有效集，且?坌va∈Va，vb∈Vb，Ei+∈E∩W+(va，vb)，其中W+(va，vb)是從點(diǎn) va到點(diǎn)vb的最短路徑，即Ei+∈Ei(Va，Vb)。

3) 設(shè)定Em=W+(va，vb)∈Ei(Va，Vb)為點(diǎn)va到點(diǎn)vb的最短路徑集，Vm∈Vi為點(diǎn)va到vb的最短路徑所經(jīng)點(diǎn)集。

4) 設(shè)Ee∈Ei(Va，Vb)為塊Va到塊Vb中出現(xiàn)異常的路徑集，Ve∈Vi為其中的異常點(diǎn)集。

5) 設(shè)Vc∈Vi，Ec∈Ei(Va，Vb)是塊Va到塊Vb中需要?jiǎng)h除的無(wú)用的點(diǎn)集和路徑集。

3.3 算法描述

1) //初始化

Em=;

Vm=;

2) //計(jì)算需刪除點(diǎn)集Vc和需刪除路徑集Ec并得到新的點(diǎn)集和路徑集Vi，

Ei(Va，Vb)

for(int i = 0;i

Dijkstra(G，Vi，Ei，Vmi，Emi);//通過(guò)Vi，Ei求最短路徑得到所經(jīng)路徑點(diǎn)集Vmi和路徑集Emi

if(i=0){

Vc=Vi-Vmi;

Ec=Ei-Emi;}

else

{Vc=(Vi-Vmi)∩Vc;

Ec=(Ei-Emi)∩Ec;}

Vi=Vi-Vc;

Ei=Ei-Ec;}

4 在交通系統(tǒng)中的應(yīng)用描述

在交通系統(tǒng)中應(yīng)用改進(jìn)后的Dijkstra算法可計(jì)算出最短路徑，但對(duì)于所得的最短路徑還要根據(jù)當(dāng)前交通信息做出分析，假設(shè)根據(jù)當(dāng)前時(shí)間點(diǎn)，可取得交通異常信息(異常點(diǎn)集、異常路徑集和異常處理時(shí)間)，因此，根據(jù)車(chē)速等信息得到的具體分析步驟如下:

1) 根據(jù)改進(jìn)后的算法求得最短路徑，得到所經(jīng)路徑的點(diǎn)集Vm及路徑集Em;

2) 判斷Vm中有否異常地點(diǎn)并判斷Em中有否異常路徑，即

if Vm∩Ve=，Em∩Ee=

then返回最短路徑集Em和路徑點(diǎn)集Vm，算法結(jié)束;

else執(zhí)行(3)

3) 計(jì)算起點(diǎn)Vs到異常點(diǎn)Ve之間路徑長(zhǎng)度Wse，并根據(jù)車(chē)速等信息計(jì)算tse=Wse/v，判斷tse與異常te大小:

If tse>te，則表明在車(chē)輛到達(dá)異常地段時(shí)，異常情況已經(jīng)處理完畢，車(chē)輛可以正常通過(guò)，則返回原最短路徑集Em和途徑點(diǎn)集Vm，算法結(jié)束;

Else執(zhí)行4)

4) 利用改進(jìn)的Dijkstra算法重新計(jì)算最短路徑，在計(jì)算時(shí)，在子集Vi中去掉異常點(diǎn)集Ve，即Vi*=Vi-Ve，在子集Ei中去掉異常路徑集Ee，即Ei*=Ei-Ee，得到新的最短路徑集Em*和途徑點(diǎn)集Vm*;

5) 根據(jù)車(chē)速計(jì)算走新的路徑所需時(shí)間tm*，以及走舊的路徑加上等待事故處理時(shí)間tm+te，判斷大小，決定取哪條路徑，即

If tm*>tm+te，走原來(lái)的路徑，返回原最短路徑集Em和途徑點(diǎn)集Vm，算法結(jié)束;

Else 走新得到的最短路徑，返回新的最短路徑集Em*和途徑點(diǎn)集Vm*，回到步驟2)，直至算法結(jié)束。

5 仿真實(shí)驗(yàn)

圖1為長(zhǎng)春市某地區(qū)地圖，現(xiàn)要求求出從南湖廣場(chǎng)(A點(diǎn))至長(zhǎng)飛醫(yī)院(B點(diǎn))的最短路徑。利用GIS地圖信息，根據(jù)改進(jìn)后的Dijkstra算法，將地圖中的路徑集{Ei}，地點(diǎn)點(diǎn)集{ Vi}定義如下:

{Ei}={南湖大路，前進(jìn)大街，繁榮路，福搶劫，南湖新村西街，南湖新村中街，南湖新村東街，湖濱街，人民大街……};

{Vi}={南湖廣場(chǎng)，松花江大學(xué)，吉林省郵電學(xué)校，吉林大學(xué)，東北師范大學(xué)第二附屬小學(xué)，吉林省第二實(shí)驗(yàn)學(xué)校，技工學(xué)校，長(zhǎng)春華僑飯店，大佛寺，吉林省實(shí)驗(yàn)中學(xué)，長(zhǎng)春市育文中學(xué)，吉林省總工會(huì)，長(zhǎng)飛醫(yī)院，威尼斯花園……};

假定交通異常信息中的Ve，Ee以及異常處理時(shí)間如下:

Ve={吉林省實(shí)驗(yàn)中學(xué)，吉林省郵電學(xué)校，吉林省第二實(shí)驗(yàn)學(xué)校};

Ee={前進(jìn)大街與繁榮路交匯路段，南湖新村西街，南湖大路與人民大街交匯路段};

{te}={吉林省實(shí)驗(yàn)中學(xué)te=15min，吉林省郵電學(xué)校te=5min，吉林省第二實(shí)驗(yàn)學(xué)校te=8min}。

利用改進(jìn)的Dijkstra算法計(jì)算最短路徑，得到第一個(gè)最短路徑集及途經(jīng)點(diǎn)集如下:

Em1={南湖大路，人民大街};

Vm1={南湖廣場(chǎng)，省吉林省實(shí)驗(yàn)中學(xué)，偉峰國(guó)際商務(wù)廣場(chǎng)，長(zhǎng)飛醫(yī)院};

根據(jù)現(xiàn)有的交通異常信息對(duì)得到的最短路徑進(jìn)行分析，在分析步驟2)中，由于結(jié)果集合和異常集合交集不為空，因此根據(jù)車(chē)速判斷時(shí)間，按照異常處理時(shí)間判斷執(zhí)行步驟4)，重新計(jì)算最短路徑，得到第二個(gè)最短路徑集及途經(jīng)點(diǎn)集如下:

Em2={前進(jìn)大街，繁榮路，人民大街};

Vm2={南湖廣場(chǎng)，吉林省郵電學(xué)校，東北師范大學(xué)第二附屬小學(xué)，威尼斯花園，長(zhǎng)飛醫(yī)院};

再次根據(jù)現(xiàn)有交通異常信息對(duì)得到的最短路徑進(jìn)行分析，發(fā)現(xiàn)結(jié)果集仍與異常集合有交集，因此再次執(zhí)行上述步驟，按照分析條件再次執(zhí)行步驟4)，得到第三個(gè)最短路徑集及途經(jīng)點(diǎn)集如下:

Em3={南湖大路，南湖新村東街，繁榮路，人民大街};

Vm3={南湖廣場(chǎng)，南湖社區(qū)商場(chǎng)，吉林省第四人民醫(yī)院，東北師范大學(xué)第二附屬小學(xué)，威尼斯花園，長(zhǎng)飛醫(yī)院};

再次分析，此時(shí)結(jié)果集與異常集合交集為空，因此將第三次計(jì)算得到的結(jié)果作為最終結(jié)果。

6 總結(jié)

通過(guò)將Dijkstra算法進(jìn)行改進(jìn)，并將得到的最短路徑與異常信息進(jìn)行分析，可以得到現(xiàn)實(shí)生活中真實(shí)的最短路徑。此方法能過(guò)避免現(xiàn)實(shí)中出現(xiàn)的很多交通異常狀況，為交通出行者提供具有一定實(shí)時(shí)性和實(shí)效性的交通信息，因此在現(xiàn)實(shí)中，此方法有一定的可推廣性。但是由于現(xiàn)實(shí)生活中地圖信息復(fù)雜，在應(yīng)用此方法的時(shí)候可能會(huì)對(duì)定義的路徑集合與地點(diǎn)點(diǎn)集的生成有一定的影響，同時(shí)計(jì)算量也比較龐大，因此在未來(lái)的研究中，對(duì)于地圖信息與數(shù)據(jù)的結(jié)合仍需改進(jìn)。

參考文獻(xiàn):

[1] 王紅梅，胡明，王濤.數(shù)據(jù)結(jié)構(gòu)(C++版)[M].北京:清華大學(xué)出版社，2005:211-212.

[2] 王峰，游志勝等.Dijkstra及基于Dijkstra的前N條最短路徑算法在智能交通系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2006(9):203-208.

[3] 臧利林，賈磊.城市交通智能控制優(yōu)化算法[J].中國(guó)公路學(xué)報(bào)，2006，19(6):97-101.

[4] 柳春光，褚雪松，何雙華.交通系統(tǒng)智能決策的算法研究[J].自然災(zāi)害學(xué)報(bào)，2007，16(3):132-136.

[5] 葉青，陳閎中.智能交通中的高效最短路徑搜索算法[J].計(jì)算機(jī)工程與應(yīng)用 2007，43(9):205-207.

[6] 張海林，顧一中.智能交通中GPS移動(dòng)系統(tǒng)設(shè)計(jì)方案研究[J].微計(jì)算機(jī)信息 2007，23(4):231-232.

[7] 史樂(lè)，李輝，原江波.基于消息通信的多智能體系統(tǒng)的應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用，2008，28(2):531-534.