改進Dijkstra算法在公共交通出行的研究

2018-11-21 04:39:54張本俊周海嬌劉淑琴

物聯網技術 2018年11期

張本俊，周海嬌，劉淑琴

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

0 引言

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

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

1 國內外研究現狀

Dijkstra算法通常用來計算加權圖中指定節點到其他頂點間的最短距離，算法需遍歷所有節點集合，且實現一次后沒有為以后的選擇留下任何信息，效率較低，尤其在節點數目大時耗時較長，其時間復雜度為O（N2）。

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

在換乘方面，目前仍存在下列問題：

（1）只考慮了公交站點，即如何到達，忽略了站點間換乘的距離，而這段距離也應計算在時間損耗中；

（2）一般提供的查詢方案以最少換乘優先，沒有考慮到用戶的人性需求，例如時間最優和票價最優；

（3）針對大城市，其公交地鐵線路尤其復雜，數據較多，目前沒有較好的優化算法來解決查詢時間過長的問題。

（4）現共享單車盛行，以往的網頁查詢中沒有考慮單車加入到公共交通出行方式中的問題。

2 改進Dijkstra算法的研究

2.1 優化思路

（1）本文將相近站點之間的換乘時間考慮進去，增加多種交通方式而非單一的公交方式。

（2）應用改進Dijkstra算法求解任意兩點間的最短路徑問題時，考慮站點間乘客換乘所步行的距離，根據用戶需求智能分析線路，提供第三種換乘方案——少步行。

（3）傳統Dijkstra算法采用鄰接矩陣來存儲數據，空間浪費較多，算法時間復雜度大。本文采用鄰接表法存儲數據，以優化存儲結構；使用優先隊列法排序，降低算法時間復雜度，提高算法執行效率。

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

2.2 改進算法描述

借用文獻[2]中的內容，對改進的Dijkstra算法進行描述，其不僅能計算加權圖中任意兩個頂點間的最短路徑，而且更易在計算機上實現，改進Dijkstra算法如下：

（1）初始化，輸入起始源點s，輸入目的點t。從有向加權圖G=（V，E）中所有節點的集合S中讀取數據，找出距起始點最近的子節點；

（2）將該點子節點距離起始點的距離值進行遍歷，并求出最小值dj；

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

Dijkstra算法流程如圖1所示。

圖1 Dijkstra算法流程圖

在代碼定義部分，先定義最大頂點個數max、定點個數n和邊結點結構體arnode，其中vertex是和表頭結點相鄰的頂點編號數，weight是連接兩頂點的邊的權值（三種方案的weight權值不同）。其次，定義頂點結點結構體venode，其中vex是當前頂點的編號，f i rarc是與該節點相連的第一個節點組成的邊值。最后，定義INF值等于0xfffff，father[a]是每個頂點的父親節點，visited[max]用來判斷起始源點s是否已經在最短路樹中。noded[max]是起始源點s到其他頂點的距離，priority_queue q表示優先隊列stl。

2.3 算法的程序實現

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

void Dijkstra（int s） //傳入源頂點

{

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

{

d[i].id = i；

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

father[i] = -1； //每個頂點均無父節點

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

}

d[s].weight = 0； //最短路權值為0

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

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

{

node cd = q.top（）； //取最小距離頂點

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；

}

相對于傳統的Dijkstra算法采用稀疏矩陣進行數據存儲，上述代碼采用鄰接表的鏈式存儲結構[6]，使用兩個數組進行存儲，一個存儲所求起始源點s到其他頂點的最短路值，另一個存儲暫時沒有排序的節點，節省存儲空間，提高算法的執行效率。

3 改進算法論證與分析

3.1 算法論證實例1

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

圖2 南昌站點信息（路程權值）有向圖

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

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

圖3 南昌站點信息（時間權值）有向圖

表1 實例1最佳方案

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

3.2 算法論證實例2

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

其中相同站點出現兩次表示站內換乘，例如48->48，同樣將圖4所示的路程權值改為時間權值。利用改進的Dijkstra算法可求得時間最優方案解，重復以上步驟，算出起點與終點的最佳路徑，得出最佳方案，見表2所列。

表2 實例2最佳方案

其中，最少換乘有2種可選方案，系統優先推薦其中耗時最短和少步行的路線，時間最優和最少換乘方案步行推薦單車出行。算法時間對比見表3所列。

表3 算法時間對比

可以看出，不論簡單或復雜的地鐵公交網絡，運用改進后的算法均能提供上述三種查詢方案，并大大減少了算法運行時間，驗證了方案的可行性。

圖4 北京站點信息（路程權值）有向圖

3.3 空間復雜度分析

傳統的Dijkstra算法采用稀疏矩陣存儲，數據存儲量為n2，其中n是加權網絡圖中的節點數，這種計算方法不僅浪費時間，還占用了較大的存儲空間。本文采用鄰接表的鏈式存儲結構[6]，使用兩個數組進行存儲，一個存儲所求起始源點s到其他頂點的最短路值，另一個存儲暫時沒有排序的節點。最終算法空間復雜度是O（e+4n），e=2.718 281 828 459。改進的Dijkstra算法與傳統算法相比，不僅節省了存儲空間，更提高了算法的執行效率。

3.4 時間復雜度分析

傳統Dijkstra算法中廣度優先搜索法需要訪問所有節點，耗時長。而改進的Dijkstra算法只需查找待排序點和堆排。運行時間主要由已標記點的鄰接點集合中元素的數量決定，且該數量值小于未標記集合中的元素數量值，查找次數至多為e次。改進算法中每次調整的時間復雜度不大于滿二叉樹的高度log2n。整個過程一共迭代執行n次，最大運行時間是O（n（log2n+e））。因此改進的Dijkstra算法有效減少了計算次數與比較次數，降低了算法的時間復雜度。改進前后算法復雜度對比見表4所列。