張本俊，周海嬌，劉淑琴

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

0 引 言

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

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

1 國內外研究現(xiàn)狀

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

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

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

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

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

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

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

2 改進Dijkstra算法的研究

2.1 優(yōu)化思路

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

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

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

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

2.2 改進算法描述

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

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

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

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

Dijkstra算法流程如圖1所示。

圖1 Dijkstra算法流程圖

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

2.3 算法的程序實現(xiàn)

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

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

{

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

{

d[i].id = i；

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

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

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；

}

}

}

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

3 改進算法論證與分析

3.1 算法論證實例1

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

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

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

其算法結果如下：把起點與下一節(jié)點相連的所有路線依次進行比較，從中選出最佳路徑。再以最佳路徑為起點，依次比較與之相連的路線，再次得到最佳路徑。實例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號線。

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

表2 實例2最佳方案

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

表3 算法時間對比

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

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

3.3 空間復雜度分析

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

3.4 時間復雜度分析

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

表4 改進前后算法復雜度對比

4 結 語

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

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

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

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