現在的公共交通越來越方便，很多城市都有地鐵，日常使用的地圖App都提供了地鐵線路換乘方案的功能，只要輸入起點和重點，App就能給出你換乘的方案，可是這個功能背后的算法又是怎么樣的呢。這篇文章將會告訴你。

說到最短路徑算法不外乎就是那么幾種，廣度優先深度優先Dijkstra之類的，這篇博客將會講述Dijkstra算法，其他的最短路徑算法我的其他文章也自己討論過，在這里不過多說了。寫這篇文章主要是因為我看其他的關于講Dijkstra算法的博客都停留在算法階段，代碼可以用，但是實用價值不多，那么這篇文章會直接帶你來實現一個上海地鐵換乘規劃算法。

數據獲取

文章中的所有代碼都上傳到了GitHub，代碼中有一個MetroRequester模塊會自動連接上海地鐵的官網（http://www.shmetro.com/）來下載所有的站點信息。request_shanghai_metro_data()函數會返回一個StationManager和一個LineManager對象。

StationManager實例是用來獲取站點信息的，存放著上海地鐵的344個站點和每個站點的地鐵線路，比如 人民廣場 站有 1，2，8 號地鐵線。

LineManager對象存放的的是地鐵線路和站點之間的關系，也就是說每條線路有什么站是存在這個對象中的。這個對象提供了一個計算兩個直達站點最短需要的站數的函數，比如莘莊到徐家匯，函數會計算出來最短路徑為7站，因為可以坐1號線直達，但是不能計算出非直達站點的最短站數，比如莘莊到靜安寺，這兩站需要乘坐1號線并且換乘其他線路才能到達。

對于單次的路徑，我抽象了一個Route類，他的實例儲存著起始站，終點站，乘坐的線路，和站數，比如下圖對應的實例：代表從徐家匯乘坐1號線經過5站到達人民廣場。

圖的二維數組展現

那么基礎的數據結構已經設計好了，那么現在來開始講算法吧，首先我們先把問題簡化一下吧。暫時只討論，徐家匯，陜西南路，漢中路，曲阜路四站，用到的地鐵線路只有1號線（紅色）和12號線（綠色）。

處理路徑問題的時候用到的數據結構為圖（Graph），那么我們來畫出這個圖，四個站分別為四個節點，邊長代表兩個節點之間的站的個數。

下圖中左側就是表達出來的圖，可以看到徐家匯是沒有辦法直答曲阜路的（徐家匯只有1號線，9號線，11號線2；而曲阜路只有8號線和12號線），必須通過換乘地鐵才可以。

并且，邊長代表到達另一個節點的最短距離，也就是最少需要的站的個數，在這四個站中，陜西南路到達漢中路有兩個直達方案：

• 直接乘坐12號線經過南京西路到達漢中路

• 直接乘坐1號線經過黃陂南路，人民廣場新閘路到達漢中路

我直接忽略了第二個方案，因為第二個方案不會有人去乘坐的，因為12號線只要坐兩站就到而1號線要做4站。

通過左邊的圖，我們可以使用一個二維數組來表示其中的關系，右邊的表可以表示，行代表起始站，列代表終點站。比如第一排第三列代表徐家匯到漢中路要經歷7站，第一排第四列代表徐家匯到曲阜路并沒有直達方案，所以是一個無限符號，這張表一般被成為臨街矩陣，在程序中可以抽象為一個二維數組，我將他稱為v_matrix

Dijkstra

Dijkstra是一個最短路徑算法，他的核心就是邊的松弛

舉一個例子，現在我要計算出來徐家匯到曲阜路的最短路徑，那么首先我們要算出徐家匯到所有地方的最短路徑。那么首先把表格的第一列拿出來代表徐家匯為起點。在程序中第一列可以抽象為一個1維數組，我將他命名為dis數組，代表distance。

首先找到離徐家匯最近的一個頂點，是陜西南路，那么徐家匯到陜西南路最短距離為3就已經確認，因為陜西南路是離徐家匯最近的一個頂點，所以兩點之間不可能存在一個比這3站還近的中專線路，畢竟兩點之間線段最短。

然后接下來就是漢中路頂點。我們不妨先看看陜西南路頂點都有哪些邊通向別的頂點，陜西南路可以通往漢中路和徐家匯，呢么有沒有一種方案能夠通過陜西南路來縮短徐家匯直達漢中路的7站距離呢？

通過觀察鄰接矩陣v_matrix，有的，從徐家匯到陜西南路，再從陜西南路到漢中路只需要走5站，要優于徐家匯直達漢中路的7站，在代碼層面這是在比較 dis[2] 與dis[1] + v_matrix[1][2]的大小

我們發現，?dis[2] = 7 , 大于 dis[1] + v_matrix[1][2] = 5于是我們更新dis[2]為5，于是徐家匯到漢中路的最短距離確認為5, 這個過程稱之為邊的松弛。

同理，我們可以通過判斷 dis[2] + v_matrix[2][3] = 6 ，小與代表曲阜路的dis[3] = 無窮大。將曲阜路的路徑縮短為6.

至此所徐家匯頂點到其余各頂點的最短路徑就求出來了。

更詳細一點的講解可以看這篇文章:

https://www.cnblogs.com/GnibChen/p/8875247.html

代碼的實現

上面就是基本的算法，可是如果dis數組和v_matrix鄰接矩陣中只有一個整數代表最短距離的話，這段代碼還是沒什么用的，我想知道徐家匯到曲阜路怎么走，如果像上面那樣編程的話程序只會告訴我最短距離為6站，沒有任何用途。

所以為了實現能夠讓程序記住換乘的路徑，我抽象出了一開始提到的Route對象，代表一個直達的路徑，在v_matrix數組中的每一個元素都是一個Route對象實例，當可以直達的時候，這個實例的stops為最短的站數，當不可以直達的時候stops為9999代表無限大。

并且dis數組也不是只保存了松弛過后邊的長度，而是保存了一個鍵值對，key為最短邊的長度，value為一個數組，儲存著若干個Route實例，遍歷這個數組即可得到所有的換乘方案。比如下圖的結構代表從徐家匯到上海科技館的換乘方案，要經歷10站，先做11號線到江蘇路，再從江蘇路換乘2號線到上海科技館。

其余的代碼直接在Github上看，不做多余的講解了。

優化

上面其實就是Dijkstra的核心了，不過，要是憑著上面的講解真的能夠寫出足夠優秀的地鐵換乘規劃算法嗎？

答案是否定的，上面講解到通過松弛將徐家匯到漢中路的站數縮短到了5站，代價是換乘一次，本來徐家匯是可以乘坐1號線直達漢中路的，只是多了兩站而已，但是我們的算法卻偏偏選擇了換乘。在真實生活中，我是不會去為了少兩站換乘的，畢竟換乘還要等下一班地鐵還要走很多路，陜西南路1號線換乘10號線或者12號線可有你走的了。

同樣再試一下莘莊到漢中路，這兩個站是可以通過一號線直達的。跑一下程序：

可以看到算法并沒有給出一號線直達的方案，而是選擇了換乘兩次，所以這樣算出來的方案非常不切實際，歸根究底，我們沒有考慮到換乘的巨大代價。

所以我引入了一個偏執值bias來表示換乘的代價，我將他設置為3，代表換乘一次和坐三站花費的時間等價。

回到徐家匯到漢中路的問題，在上文我是這么寫的：

dis[2] = 7 , 大于 dis[1] + v_matrix[1][2] = 5于是我們更新dis[2]為5

這次計算我們引入bias為3

dis[2] = 7?；?dis[1] + v_matrix[1][2] + bias = 8, 可以看到在比較的時候引入一個bias值導致這次計算出來直達的7站是一個最優方案，因為換乘的邊長由5變成了8。

通過這個右滑，來再看看莘莊到漢中路的方案：

這一次算法給出了合理的最優方案。

當然這樣可能也不太完美，因為對于頂點之間的邊長，我僅僅是使用了站點數來表示，如果用真實距離來表示會更加精準，或者用不同的站到不同的站的經歷時間來表示長短也是不錯的選擇。

尾巴

那么換乘算法已經有了，你有沒有想過地圖App是怎么確定你周圍最近的地鐵站的呢？沒有想法的同學可以看我幾年前寫過的博客：周圍的餐館有哪些？GeoHash算法

這個項目的Github地址:?https://github.com/Yigang0622/Metro-Transfer-Algorithm

總結

以上是生活随笔為你收集整理的人民广场怎么走？地铁换乘算法的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。