改進(jìn)的Dijkstra最短路徑算法在GIS-T中的研究與實(shí)現(xiàn)

戴文博 殷招偉 錢俊彥

（桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西 桂林 541004）

改進(jìn)的Dijkstra最短路徑算法在GIS-T中的研究與實(shí)現(xiàn)

戴文博 殷招偉 錢俊彥

（桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西 桂林 541004）

Dijkstra最短路徑算法廣泛應(yīng)用于交通運(yùn)輸和網(wǎng)絡(luò)優(yōu)化等領(lǐng)域，但是在實(shí)際應(yīng)用的過程中仍存在一些不足。文章針對(duì)道路擁擠、交叉路口等待和單行道限行等方面提出了一種改進(jìn)的基于時(shí)間最短的最短路徑算法。傳統(tǒng)的最短路徑算法中圖的頂點(diǎn)是抽象的，不含權(quán)重的，改進(jìn)的算法中圖的頂點(diǎn)是有權(quán)值的，用來表示道路交叉口的等待時(shí)間。通過編程實(shí)現(xiàn)該算法，實(shí)驗(yàn)結(jié)果表明，道路擁擠、交叉口等待和單行道限行對(duì)交通路徑選擇有很大影響。因此，改進(jìn)的算法求得的最短時(shí)間路徑更加符合實(shí)際，具有一定的應(yīng)用價(jià)值。

Dijkstra最短路徑算法；最短時(shí)間路徑；交通運(yùn)輸；網(wǎng)絡(luò)優(yōu)化

隨著城市化進(jìn)程的加快，城市交通網(wǎng)絡(luò)的規(guī)模也在不斷擴(kuò)大，交通設(shè)施日益發(fā)達(dá)，但這也使城市交通變得異常復(fù)雜。這也就促使了交通地理信息系統(tǒng)（GIS-T，Geographic Information System for Transportation）的應(yīng)用日益廣泛。GIS-T是地理信息系統(tǒng)（GIS）[1]在勘測(cè)設(shè)計(jì)、道路規(guī)劃和管理等領(lǐng)域中的具體應(yīng)用，它充分考慮了現(xiàn)有的交通網(wǎng)絡(luò)的特征，過濾掉 GIS多余的功能，減少冗余，更加高效、快捷的管理和規(guī)劃交通[2]。為了能夠使得資源和時(shí)間得以充分利用，必須考慮到車輛路徑規(guī)劃。車輛路徑規(guī)劃問題一般指的是對(duì)一系列的起點(diǎn)和終點(diǎn)，調(diào)用一定的車輛，組織選擇一條或多條適當(dāng)?shù)男熊嚶肪€，使車輛有序的通過它們，在滿足指定的約束條件下（如距離最短、時(shí)間最短、費(fèi)用最低等），爭(zhēng)取實(shí)現(xiàn)如車輛行駛里程最短、運(yùn)行時(shí)間最短、運(yùn)費(fèi)最低等目標(biāo)[3]。而 GIS-T的重點(diǎn)之一就是路徑規(guī)劃分析，因此，交通路徑規(guī)劃問題必然成為 GIS-T的研究熱點(diǎn)之一，而路徑的選擇取決于多種因素，較常見的有三種：車輛行駛距離、車輛所需費(fèi)用和車輛行駛時(shí)間。在具體應(yīng)用中，有些司機(jī)愿意選擇距離最短，有些司機(jī)愿意選擇費(fèi)用最少，有些司機(jī)愿意選擇最短出行時(shí)間。

無論采用何種標(biāo)準(zhǔn)，最優(yōu)路徑規(guī)劃最終都可以歸結(jié)為在特定道路網(wǎng)中尋找具有最小代價(jià)的最短路徑問題[4]。

因此，就需要合理的規(guī)劃交通路線以滿足人們需求。本文就如何使得行駛時(shí)間最短進(jìn)行了討論。

在研究問題的過程中，可以將實(shí)際的交通網(wǎng)絡(luò)模型化成網(wǎng)絡(luò)圖，根據(jù)圖論的相關(guān)知識(shí)，交通網(wǎng)絡(luò)中的兩點(diǎn)之間的最短路徑就可以用圖中頂點(diǎn)之間的最短路徑表示。圖的最短路徑問題由很多國(guó)內(nèi)外學(xué)者進(jìn)行了深入的研究，提出了許多種最短路徑算法，其中Dijkstra提出了一個(gè)按路徑長(zhǎng)度遞增的次序產(chǎn)生的最短路徑算法是目前已知的理論上最完善、應(yīng)用最多的算法[5]。這些算法解決了兩點(diǎn)之間的最短路徑問題，但是有時(shí)需要的并不是兩點(diǎn)之間的最短距離而是追求時(shí)間和速度上的需求。那么我們就需要考慮將圖中的邊或弧的權(quán)值由行駛時(shí)間替換路段距離，對(duì)于道路擁擠和交叉路口紅綠燈等待時(shí)間也是需要考慮的因素，而對(duì)于某些單向限行的道路可能在一些地圖軟件中搜索到的最短路徑是不太實(shí)用的。

1 相關(guān)基礎(chǔ)知識(shí)

1.1 Dijkstra最短路徑算法

Dijkstra最短路徑算法是由荷蘭計(jì)算機(jī)科學(xué)教授迪杰斯特（E.W.Dijkstra）在1959年提出的，它被公認(rèn)為是最經(jīng)典的算法之一，也是解決最短路徑問題的基礎(chǔ)算法。它可以從某點(diǎn)到網(wǎng)絡(luò)中其余各頂點(diǎn)的路徑長(zhǎng)度依次遞增的順序產(chǎn)生最短路徑，適應(yīng)于所有弧或邊的權(quán)值為非負(fù)的圖。

Dijkstra算法的基本思想可以簡(jiǎn)單的描述為：從起始頂點(diǎn)出發(fā)，找到從起始頂點(diǎn)到其余各頂點(diǎn)中第1、第2……第n短的路徑，這樣就獲得了從起始頂點(diǎn)到其余各頂點(diǎn)的最短路徑。如果要獲得從起始頂點(diǎn)到某個(gè)頂點(diǎn)的最短距離，則直到找到這個(gè)頂點(diǎn)的最短路徑就停止，不再繼續(xù)查找[6]。

1.2 算法理論基礎(chǔ)

單源最短路徑問題，即根據(jù)最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)，在圖中求出從給定的頂點(diǎn)到其他任意頂點(diǎn)的最短路徑。最優(yōu)子結(jié)構(gòu)的性質(zhì)可以描述為：如果D(i, j)= {Vi…Vk…Vs…Vj}是從頂點(diǎn)i到j(luò)的最短路徑，k和s分別是這條最短路徑上的中間結(jié)點(diǎn)，那么D(k,s)必定是從頂點(diǎn)k到頂點(diǎn)s的最短路徑距離[7]，下面證明該性質(zhì)的正確性。

假設(shè)D(i, j)={Vi…Vk…Vs…Vj}是從頂點(diǎn)i到j(luò)的最短路徑，D(k, s)不是從k到s的最短路徑距離。那么則有D(i, j) =D(i, k)+D(k, s)+D(s, j)，而D(k, s)不是最短的，故存在另一條從k 到s比D(k, s)更短的D’(k, s),那么D’(i, j)=D(i, k) +D’(k, s)+D(s, j) ,由于D’(k, s)＜ D(k, s),那么D’(i, j)＜ D(i, j)，這與D(i, j)是從i到j(luò)的最短距離相矛盾，從而該性質(zhì)得證。

根據(jù)以上性質(zhì)可知，如果在一條從 i到 j的最短路徑{Vi…Vk，Vj}，那么{Vi…Vk，Vj}，Vk是Vj的前驅(qū)結(jié)點(diǎn)，那么{Vi…Vk}也必然是從i到k的最短路徑，據(jù)此，Dijkstra提出的一個(gè)按路徑長(zhǎng)度遞增的次序產(chǎn)生的最短路徑算法，如對(duì)于起點(diǎn)V0，首先選擇與其直接相連的頂點(diǎn)中長(zhǎng)度最短的頂點(diǎn)Vi，那么可得V0到Vj的最短距離Distance[j]= min{Distance[j] , Distance[j]+matrix[i][j]}[8]。

翻轉(zhuǎn)課堂教學(xué)可以解決上述問題，以學(xué)為本建設(shè)優(yōu)質(zhì)的在線開放課程，開啟課程資源共享與應(yīng)用模式，學(xué)生課下先學(xué)習(xí)老師提供的基礎(chǔ)知識(shí)，如果有問題就可以記錄下來，在課堂上由老師答疑或同學(xué)討論來解決。翻轉(zhuǎn)課堂通過把傳統(tǒng)的課堂學(xué)習(xí)和線上學(xué)習(xí)的優(yōu)勢(shì)結(jié)合在一起，實(shí)現(xiàn)線上線下混合式教學(xué)，可以更好地加強(qiáng)面對(duì)面的互動(dòng)，培養(yǎng)學(xué)生團(tuán)結(jié)協(xié)作的能力，提高教學(xué)效果，開啟學(xué)生深度學(xué)習(xí)，滿足不同學(xué)生對(duì)象的學(xué)習(xí)需求[5]。

2 最短時(shí)間路徑算法

2.1 道路網(wǎng)的模型建立

對(duì)于前面提到道路擁堵而導(dǎo)致的時(shí)延，我們可以通過交通部門發(fā)布的實(shí)時(shí)數(shù)據(jù)來獲取該道路的實(shí)時(shí)平均速度，從而根據(jù)路長(zhǎng)，求得該段線路的車輛行駛時(shí)間。將交通網(wǎng)絡(luò)轉(zhuǎn)換為網(wǎng)絡(luò)圖，那么該段路線車輛行駛時(shí)間即為網(wǎng)絡(luò)圖中兩頂點(diǎn)的弧的權(quán)值；對(duì)于交叉口紅綠燈延誤的時(shí)間，可以轉(zhuǎn)換為圖中頂點(diǎn)的權(quán)值，而在傳統(tǒng)的最短路徑算法中，圖的頂點(diǎn)是沒有權(quán)重的，只起到標(biāo)識(shí)的作用，在算法中是不起作用的；對(duì)于單行線路段，可以動(dòng)態(tài)的改變有向圖中弧的方向。由此，可以得到該道路網(wǎng)的模型如圖1。

圖1 道路網(wǎng)模型圖

圖1中，圓圈分別表示各個(gè)道路網(wǎng)的頂點(diǎn)，圓圈旁的Vi （i=0，1，…，5）為各頂點(diǎn)的標(biāo)識(shí)符，圓圈中的數(shù)字表示各個(gè)交叉口的等待時(shí)間，弧段上的數(shù)字表示車輛路段行駛時(shí)間，當(dāng)圖中某兩個(gè)頂點(diǎn)分別表示起點(diǎn)和終點(diǎn)，延誤時(shí)間不需計(jì)入。

2.2 改進(jìn)的算法思想

由于在傳統(tǒng)的最短路徑算法中，圖的頂點(diǎn)是沒有權(quán)值的，因此，我們需要在定義圖的結(jié)構(gòu)過程中額外增加一個(gè)vertex[MaxVexNum]數(shù)組來存儲(chǔ)圖中所有頂點(diǎn)的權(quán)值來解決交叉口等待時(shí)間[9]。然后根據(jù)上面的性質(zhì)假設(shè)存在G=＜V,E＞，源頂點(diǎn)V0，Distance[i]記錄的是V0到Vi最短時(shí)間，path[i]記錄的是V0到Vi前驅(qū)的一條最短路徑，matrix是用來表示帶權(quán)有向圖的鄰接矩陣，matrix[i][j]表示弧＜Vi, Vj＞上的權(quán)值。若＜Vi, Vj＞不存在，則將matrix[i][j]置為∞或者一個(gè)相對(duì)較大的值。求解V0到其余各頂點(diǎn)的最短時(shí)間路徑，由于在改進(jìn)的算法中，圖的頂點(diǎn)是有權(quán)重的，因此，在計(jì)算源點(diǎn)到各頂點(diǎn)的最短時(shí)間時(shí)需要將圖的頂點(diǎn)計(jì)算進(jìn)去?；舅枷肴缦拢?/p>

（1）初始化頂點(diǎn)集S={V0}和T=V-S，集合S中存放已經(jīng)找到的最短時(shí)間路徑的頂點(diǎn)而集合T中存放余下的頂點(diǎn)。

（2）不斷的從集合T中選擇頂點(diǎn)V0到頂點(diǎn)Vu的最短時(shí)間路徑長(zhǎng)度即Distance[u]最小的頂點(diǎn)Vu加入到集合S中。

（3）更新V0到集合T中剩下的頂點(diǎn)的最短時(shí)間路徑長(zhǎng)度，Distance[j]=min{Distance[j],Distance[j]+matrix[i] [j]+vertex[i]},這是本算法的核心部分。

（4）重復(fù)上面的(2)、(3)兩步驟，直到S=V結(jié)束。

2.3 算法求解過程針對(duì)圖1，算法的求解過程如下表1所示，V0到各個(gè)頂點(diǎn)的最短時(shí)間路徑分別是：V0-＞V2，最短時(shí)間為10；V0-＞V4，最短時(shí)間為30；V0-＞V2-＞V3，最短時(shí)間為80；V0-＞V2-＞V3-＞V5，最短時(shí)間為95。

表1 V0到各個(gè)終點(diǎn)的Distance值和最短路徑求解過程

2.4 算法部分代碼

在傳統(tǒng)的最短路徑算法中，圖頂點(diǎn)沒有權(quán)重，因此，頂點(diǎn)在算法中不起作用，但是在改進(jìn)的算法中，圖的頂點(diǎn)是有權(quán)重的，因此，在圖結(jié)構(gòu)定義的時(shí)候，添加一個(gè) vertex[Max Vexnum]數(shù)組來表示頂點(diǎn)的權(quán)重。

3 實(shí)驗(yàn)結(jié)果與分析

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

本文的仿真實(shí)驗(yàn)環(huán)境：處理器為Inter(R) Core(TM)2 Duo CPU/2.93GHz,內(nèi)存為2.00GB的PC機(jī)，根據(jù)上述算法，編寫的程序代碼在VS2010集成環(huán)境下運(yùn)行結(jié)果圖2和圖3。

3.2 實(shí)驗(yàn)結(jié)果分析

本文是用車輛行駛的時(shí)間來替換路段長(zhǎng)度表示路徑上的權(quán)重，由此還是轉(zhuǎn)換為求解網(wǎng)絡(luò)最優(yōu)路線問題。由表1和圖3，可以算法的求解過程和程序執(zhí)行過程是一致的。由圖2和圖3可知，在傳統(tǒng)的算法中，V0到V3的最短路徑為V0-＞V4-＞V3，計(jì)算權(quán)值為50，V0到V5的最短路徑為V0-＞V4-＞V3-＞V5，計(jì)算權(quán)值為60；而在改進(jìn)的算法中，V0到V3的最短路徑為V0-＞V2-＞V3，計(jì)算權(quán)值為 80，V0到 V5的最短路徑為V0-＞V2-＞V3-＞V5，計(jì)算權(quán)值為95。這就充分說明了圖中頂點(diǎn)有無權(quán)值，對(duì)最短路徑有較大的影響，即交叉口的交通紅路燈等待時(shí)間對(duì)最短時(shí)間路徑的選擇有很大的影響，對(duì)于單行線，只是改變有向圖中的弧的方向，那么只需在搜索最短時(shí)間路徑前更新鄰接矩陣matrix[i][j]中對(duì)應(yīng)的值。因此改進(jìn)的算法更貼近實(shí)際。而對(duì)于算法執(zhí)行的時(shí)間，由于結(jié)點(diǎn)個(gè)數(shù)少，兩個(gè)算法的執(zhí)行時(shí)間都在納秒級(jí)別。改進(jìn)后的算法時(shí)間復(fù)雜度O(n2)與傳統(tǒng)最短路徑算法的復(fù)雜度一致。

圖2 傳統(tǒng)最短路徑算法的執(zhí)行結(jié)果

圖3 改進(jìn)的算法的執(zhí)行結(jié)果

4 結(jié)語

本文主要討論了Dijkstra最短路徑算法并在其基礎(chǔ)上提出了基于時(shí)間的最短時(shí)間路徑算法，傳統(tǒng)的算法網(wǎng)絡(luò)圖中頂點(diǎn)是沒有權(quán)重的，而改進(jìn)的算法增加了頂點(diǎn)的權(quán)重來表示交叉口紅綠燈等待時(shí)間，該算法主要解決了道路擁擠、交叉路口紅綠燈等待和單行線路段限制的路徑規(guī)劃問題，并通過算法編程實(shí)驗(yàn)證明，使得搜索到的最短時(shí)間的路徑更加的符合實(shí)際，更能滿足人們的需求，具有較大的應(yīng)用價(jià)值。

[1] 劉學(xué)軍,徐鵬.交通地理信息系統(tǒng)[M].北京:科學(xué)出版社, 2006.

[2] Miller H J, Shaw S L. Geographic information systems for transportation: principles and applications[M]. Oxford University Press,2001.

[3] 孫麗君,胡祥培,王錚.車輛路徑規(guī)劃問題及其求解方法研究進(jìn)展[J].系統(tǒng)工程,2006,(11):31-37.

[4] 林清巖.智能交通中車輛最優(yōu)路徑規(guī)劃策略研究[D]. 吉林大學(xué),2013.

[5] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京:清華大學(xué)出版社,1997.

[6] Chuan-xiang REN,Xin-gang HAO,Ying-rui Wang. Research on the Optimization and Simulation of the Shortest PathBased on Algorithm of Dijkstra[J]. Journal of Measurement Science and Instrumentation, 2010.

[7] 胡運(yùn)權(quán).運(yùn)籌學(xué)教程(第 3版)[M].北京:清華大學(xué)出版社,2007.

[8] 秦鋒,湯亞玲.數(shù)據(jù)結(jié)構(gòu):C語言版[M].北京:清華大學(xué)出版社,2011.

[9] 陳悅.基于行程時(shí)間組合預(yù)測(cè)模型的動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)研究[D].華南理工大學(xué),2012.

Research and implementation of the improved Dijkstra shortest path algorithm in GIS-T

Dijkstra shortest path algorithm(DSPA) is widely used in fields of communication and transportation and network optimization, etc. But there are still some shortcomings in the process of practical application. We propose an improved SPA based on the minimum duration which is directing at the aspects such as congested roads, the intersection waiting and one-way street restrictions. The vertex of diagram in tradition SPA is abstract and does not contain the weight, while does and is used to represent the intersections waiting time in improved algorithm.We program to implement it and the results show that the above three aspects mentioned has a great influence on choice of the transportation route. Therefore, the shortest time path wh3ich is gained by the improved algorithm is more in line with the actual and the improved algorithm has a certain application value.

Dijkstra shortest path algorithm; the shortest time path; communication and transportation; network optimization

TP312

A

1008-1151(2015)02-0001-03

2015-01-12

戴文博，男，桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士，研究方向?yàn)镚IS-T及數(shù)據(jù)庫應(yīng)用；殷招偉，桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士；錢俊彥，桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院博士。