改進(jìn)Dijkstra算法在公共交通出行的研究

張本俊，周海嬌，劉淑琴

（江西師范大學(xué) 物理與通信電子學(xué)院，江西 南昌 330022）

0 引 言

錯(cuò)綜復(fù)雜的公交路網(wǎng)讓人心慌意亂，特別是來(lái)到人生地不熟的地方，一條最優(yōu)交通路線的重要性不言而喻。多種交通方式并存的模式將更符合現(xiàn)代化社會(huì)的需求。隨著公共交通的多元化和共享單車的盛行，人們出行考慮的不再僅僅是路程問(wèn)題，而是由時(shí)間、換乘和票價(jià)等因素決定的綜合問(wèn)題。通常同一路線的公交行程中，最大金額與最小金額差異不大，因此重點(diǎn)考慮少換乘。

Dijkstra算法是求解單源最短路徑問(wèn)題的典型算法。本文考慮到站點(diǎn)間換乘的距離和換乘票價(jià)問(wèn)題，根據(jù)用戶需求智能分析線路，實(shí)現(xiàn)人性化公交線路查詢，提供換乘方案的三種可選方向，分別是時(shí)間最優(yōu)、最少換乘和少步行。

1 國(guó)內(nèi)外研究現(xiàn)狀

Dijkstra算法通常用來(lái)計(jì)算加權(quán)圖中指定節(jié)點(diǎn)到其他頂點(diǎn)間的最短距離，算法需遍歷所有節(jié)點(diǎn)集合，且實(shí)現(xiàn)一次后沒(méi)有為以后的選擇留下任何信息，效率較低，尤其在節(jié)點(diǎn)數(shù)目大時(shí)耗時(shí)較長(zhǎng)，其時(shí)間復(fù)雜度為O（N2）。

近年來(lái)，國(guó)內(nèi)外對(duì)此算法的研究已經(jīng)相對(duì)完善，主要針對(duì)Dijkstra算法本身和應(yīng)用進(jìn)行改進(jìn)。例如，李健研究的基于Dijkstra最短路徑算法的優(yōu)化研究[1]；韓慧玲、胡紅萍研究的Dijkstra算法在公交換乘最短路徑中的應(yīng)用[2]；余震江研究的基于最短路徑Dijkstra算法的鐵路客運(yùn)中轉(zhuǎn)路徑優(yōu)化研究[3]；Joseph Kirk使用Dijkstra算法計(jì)算沿著圖的邊的最短（最少成本）路徑[4]等。

在換乘方面，目前仍存在下列問(wèn)題：

（1）只考慮了公交站點(diǎn)，即如何到達(dá)，忽略了站點(diǎn)間換乘的距離，而這段距離也應(yīng)計(jì)算在時(shí)間損耗中；

（2）一般提供的查詢方案以最少換乘優(yōu)先，沒(méi)有考慮到用戶的人性需求，例如時(shí)間最優(yōu)和票價(jià)最優(yōu)；

（3）針對(duì)大城市，其公交地鐵線路尤其復(fù)雜，數(shù)據(jù)較多，目前沒(méi)有較好的優(yōu)化算法來(lái)解決查詢時(shí)間過(guò)長(zhǎng)的問(wèn)題。

（4）現(xiàn)共享單車盛行，以往的網(wǎng)頁(yè)查詢中沒(méi)有考慮單車加入到公共交通出行方式中的問(wèn)題。

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

2.1 優(yōu)化思路

（1）本文將相近站點(diǎn)之間的換乘時(shí)間考慮進(jìn)去，增加多種交通方式而非單一的公交方式。

（2）應(yīng)用改進(jìn)Dijkstra算法求解任意兩點(diǎn)間的最短路徑問(wèn)題時(shí)，考慮站點(diǎn)間乘客換乘所步行的距離，根據(jù)用戶需求智能分析線路，提供第三種換乘方案——少步行。

（3）傳統(tǒng)Dijkstra算法采用鄰接矩陣來(lái)存儲(chǔ)數(shù)據(jù)，空間浪費(fèi)較多，算法時(shí)間復(fù)雜度大。本文采用鄰接表法存儲(chǔ)數(shù)據(jù)，以優(yōu)化存儲(chǔ)結(jié)構(gòu)；使用優(yōu)先隊(duì)列法排序，降低算法時(shí)間復(fù)雜度，提高算法執(zhí)行效率。

（4）在傳統(tǒng)Dijkstra算法中加入騎行方式，當(dāng)步行距離大于1 000 m或者乘車少于2站時(shí)，增加單車出行方案。

2.2 改進(jìn)算法描述

借用文獻(xiàn)[2]中的內(nèi)容，對(duì)改進(jìn)的Dijkstra算法進(jìn)行描述，其不僅能計(jì)算加權(quán)圖中任意兩個(gè)頂點(diǎn)間的最短路徑，而且更易在計(jì)算機(jī)上實(shí)現(xiàn)，改進(jìn)Dijkstra算法如下：

（1）初始化，輸入起始源點(diǎn)s，輸入目的點(diǎn)t。從有向加權(quán)圖G=（V，E） 中所有節(jié)點(diǎn)的集合S中讀取數(shù)據(jù)，找出距起始點(diǎn)最近的子節(jié)點(diǎn)；

（2）將該點(diǎn)子節(jié)點(diǎn)距離起始點(diǎn)的距離值進(jìn)行遍歷，并求出最小值dj；

（3）將該最小值放入集合T中，把該子節(jié)點(diǎn)放入集合H中，重復(fù)上述步驟至集合V-S為空或找到終點(diǎn)。

Dijkstra算法流程如圖1所示。

圖1 Dijkstra算法流程圖

在代碼定義部分，先定義最大頂點(diǎn)個(gè)數(shù)max、定點(diǎn)個(gè)數(shù)n和邊結(jié)點(diǎn)結(jié)構(gòu)體arnode，其中vertex是和表頭結(jié)點(diǎn)相鄰的頂點(diǎn)編號(hào)數(shù)，weight是連接兩頂點(diǎn)的邊的權(quán)值（三種方案的weight權(quán)值不同）。其次，定義頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)體venode，其中vex是當(dāng)前頂點(diǎn)的編號(hào)，f i rarc是與該節(jié)點(diǎn)相連的第一個(gè)節(jié)點(diǎn)組成的邊值。最后，定義INF值等于0xfffff，father[a]是每個(gè)頂點(diǎn)的父親節(jié)點(diǎn)，visited[max]用來(lái)判斷起始源點(diǎn)s是否已經(jīng)在最短路樹(shù)中。noded[max]是起始源點(diǎn)s到其他頂點(diǎn)的距離，priority_queue q表示優(yōu)先隊(duì)列stl。

2.3 算法的程序?qū)崿F(xiàn)

在參考文獻(xiàn)[5]中已給出偽代碼，其算法核心代碼如下：

void Dijkstra（int s） //傳入源頂點(diǎn)

{

for（int i = 1 ； i <= n ； i++）

{

d[i].id = i；

d[i].weight = INF； //設(shè)估算距離為INF

father[i] = -1； //每個(gè)頂點(diǎn)均無(wú)父節(jié)點(diǎn)

visited[i] = false； //都未找到最短路

}

d[s].weight = 0； //最短路權(quán)值為0

q.push（d[s]）； //壓入隊(duì)列中

while （!q.empty（） //隊(duì)列空，完成操作

{

node cd = q.top（）； //取最小距離頂點(diǎn)

q.pop（）；

int u = cd.id；

if（visited[u]） continue ；

visited[u] = true；

arnode * p = Ver[u].f i rarc； //松弛操作

while（p != NULL）

{

int v = p->vertex；

if（!visited[v]&&d[v].w >d[u].w+p->weight）

{

d[v].w = d[u].w+p->weight；

father[v] = u；

q.push （d[v]）；

}

p = p->next；

}

}

}

相對(duì)于傳統(tǒng)的Dijkstra算法采用稀疏矩陣進(jìn)行數(shù)據(jù)存儲(chǔ)，上述代碼采用鄰接表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)[6]，使用兩個(gè)數(shù)組進(jìn)行存儲(chǔ)，一個(gè)存儲(chǔ)所求起始源點(diǎn)s到其他頂點(diǎn)的最短路值，另一個(gè)存儲(chǔ)暫時(shí)沒(méi)有排序的節(jié)點(diǎn)，節(jié)省存儲(chǔ)空間，提高算法的執(zhí)行效率。

3 改進(jìn)算法論證與分析

3.1 算法論證實(shí)例1

選取地鐵公交線路較簡(jiǎn)單的南昌市江西師范大學(xué)瑤湖校區(qū)到紫金城為例，其中X表示江西師范大學(xué)瑤湖校區(qū)，Y表示紫金城小區(qū)，A～D表示地鐵1號(hào)線站點(diǎn)，數(shù)字1～4表示公交220站點(diǎn)，5～8表示公交3站點(diǎn)，9～11表示高鐵巴士7線站點(diǎn)，12～15表示公交816站點(diǎn)，16～17表示公交1站點(diǎn)，18～22表示公交816站點(diǎn)。其中有向圖中每?jī)牲c(diǎn)間的數(shù)值從左到右表示上述站間步行的距離（km）和時(shí)間（min）。南昌站點(diǎn)信息有向圖如圖2所示。

圖2 南昌站點(diǎn)信息（路程權(quán)值）有向圖

基于大數(shù)據(jù)分析得出，平均每人步行時(shí)間為3.6 km/h，南昌市的公交時(shí)速和地鐵時(shí)速分別為30 km/h和45 km/h。將路程權(quán)值改為時(shí)間權(quán)值，利用改進(jìn)的Dijkstra算法可求得時(shí)間最優(yōu)方案解，如圖3所示。

其算法結(jié)果如下：把起點(diǎn)與下一節(jié)點(diǎn)相連的所有路線依次進(jìn)行比較，從中選出最佳路徑。再以最佳路徑為起點(diǎn)，依次比較與之相連的路線，再次得到最佳路徑。實(shí)例1最佳方案見(jiàn)表1所列。

圖3 南昌站點(diǎn)信息（時(shí)間權(quán)值）有向圖

表1 實(shí)例1最佳方案

上述三種方案都可滿足單車出行的要求。

3.2 算法論證實(shí)例2

選取復(fù)雜地鐵公交線路的實(shí)例北京市，以中國(guó)傳媒大學(xué)到圓明園公園遺址為例，其中A表示中國(guó)傳媒大學(xué)，B表示圓明園公園遺址，1～12表示快速公交2號(hào)線站點(diǎn)，12～18表示地鐵2號(hào)線，18～25，45和54表示北京地鐵4號(hào)線站點(diǎn)，13～17表示北京地鐵10號(hào)線站點(diǎn)，18～25，45以及54表示地鐵4號(hào)線，9和26～35表示671路公交，36～48表示地鐵6號(hào)線，48和20表示地鐵9號(hào)線，49～53表示公交517路，40，55～60和20表示地鐵10號(hào)線。

其中相同站點(diǎn)出現(xiàn)兩次表示站內(nèi)換乘，例如48->48，同樣將圖4所示的路程權(quán)值改為時(shí)間權(quán)值。利用改進(jìn)的Dijkstra算法可求得時(shí)間最優(yōu)方案解，重復(fù)以上步驟，算出起點(diǎn)與終點(diǎn)的最佳路徑，得出最佳方案，見(jiàn)表2所列。

表2 實(shí)例2最佳方案

其中，最少換乘有2種可選方案，系統(tǒng)優(yōu)先推薦其中耗時(shí)最短和少步行的路線，時(shí)間最優(yōu)和最少換乘方案步行推薦單車出行。算法時(shí)間對(duì)比見(jiàn)表3所列。

表3 算法時(shí)間對(duì)比

可以看出，不論簡(jiǎn)單或復(fù)雜的地鐵公交網(wǎng)絡(luò)，運(yùn)用改進(jìn)后的算法均能提供上述三種查詢方案，并大大減少了算法運(yùn)行時(shí)間，驗(yàn)證了方案的可行性。

圖4 北京站點(diǎn)信息（路程權(quán)值）有向圖

3.3 空間復(fù)雜度分析

傳統(tǒng)的Dijkstra算法采用稀疏矩陣存儲(chǔ)，數(shù)據(jù)存儲(chǔ)量為n2，其中n是加權(quán)網(wǎng)絡(luò)圖中的節(jié)點(diǎn)數(shù)，這種計(jì)算方法不僅浪費(fèi)時(shí)間，還占用了較大的存儲(chǔ)空間。本文采用鄰接表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)[6]，使用兩個(gè)數(shù)組進(jìn)行存儲(chǔ)，一個(gè)存儲(chǔ)所求起始源點(diǎn)s到其他頂點(diǎn)的最短路值，另一個(gè)存儲(chǔ)暫時(shí)沒(méi)有排序的節(jié)點(diǎn)。最終算法空間復(fù)雜度是O（e+4n），e=2.718 281 828 459。改進(jìn)的Dijkstra算法與傳統(tǒng)算法相比，不僅節(jié)省了存儲(chǔ)空間，更提高了算法的執(zhí)行效率。

3.4 時(shí)間復(fù)雜度分析

傳統(tǒng)Dijkstra算法中廣度優(yōu)先搜索法需要訪問(wèn)所有節(jié)點(diǎn)，耗時(shí)長(zhǎng)。而改進(jìn)的Dijkstra算法只需查找待排序點(diǎn)和堆排。運(yùn)行時(shí)間主要由已標(biāo)記點(diǎn)的鄰接點(diǎn)集合中元素的數(shù)量決定，且該數(shù)量值小于未標(biāo)記集合中的元素?cái)?shù)量值，查找次數(shù)至多為e次。改進(jìn)算法中每次調(diào)整的時(shí)間復(fù)雜度不大于滿二叉樹(shù)的高度log2n。整個(gè)過(guò)程一共迭代執(zhí)行n次，最大運(yùn)行時(shí)間是O（n（log2n+e））。因此改進(jìn)的Dijkstra算法有效減少了計(jì)算次數(shù)與比較次數(shù)，降低了算法的時(shí)間復(fù)雜度。改進(jìn)前后算法復(fù)雜度對(duì)比見(jiàn)表4所列。

表4 改進(jìn)前后算法復(fù)雜度對(duì)比

4 結(jié) 語(yǔ)

（1）本文利用轉(zhuǎn)乘智能分析提供了公交地鐵交叉換乘方案的三種可選方向，分別是時(shí)間最優(yōu)、最少換乘和少步行；

（2）改進(jìn)后的Dijkstra算法克服了傳統(tǒng)算法時(shí)間冗長(zhǎng)的缺陷，雙向遍歷尋優(yōu)，減少查詢時(shí)間，增強(qiáng)了設(shè)計(jì)的可行性；

（3）大城市公交地鐵線路復(fù)雜，數(shù)據(jù)量龐大，現(xiàn)有部分網(wǎng)頁(yè)展示的查詢路線系統(tǒng)無(wú)法及時(shí)反映公交線路的改動(dòng)問(wèn)題，本文給出了良好的優(yōu)化算法來(lái)解決該問(wèn)題。

由于本算法沒(méi)有考慮到夏冬兩季的公交地鐵始末班時(shí)間不同的問(wèn)題，因此后期可用網(wǎng)絡(luò)獲取數(shù)據(jù)，根據(jù)行駛的具體時(shí)間生成不同的換乘方案。同時(shí)還可加入通過(guò)地圖數(shù)據(jù)獲取的站點(diǎn)擁擠度參數(shù)以進(jìn)一步優(yōu)化換乘方案。算法未考慮單車出行受天氣影響的程度，可通過(guò)獲取天氣權(quán)重，最終實(shí)現(xiàn)智能分析公共交通的出行查詢體系。