SQL 實現最優地鐵換乘方案：遞歸查詢與路徑搜尋演算法

前言

在城市軌道交通系統中，如何利用 SQL 查詢找出起訖站之間換乘次數最少、途經站數最少的最優路徑，是一個經典的圖論最短路徑問題。本文透過 T-SQL 的遞歸 CTE（Common Table Expression）與迴圈模擬，示範如何在關聯式資料庫中實現多條路線、多換乘站的動態路徑搜尋。

資料模型設計

範例使用單一資料表 @tb 儲存路線資訊，欄位包含：

• lineID：路線編號（1 號線、2 號線……）
• state：站名（如「廣州東」、「體育西」）
• orderid：站序，代表列車在該路線上的停靠順序

資料涵蓋 4 條路線，共同構成一個簡易的地鐵網絡。換乘站如「公園前」（1/2 號線）、「客村」（2/3 號線）、「體育西」（1/3 號線）、「萬勝圍」（2/4 號線）等，使得跨路線轉乘成為可能。

核心演算法邏輯

演算法採用「層次擴展」策略，模擬廣度優先搜尋（BFS）：

1. 初始化：從起點站（@state_start）出發，將所有屬於該站的路線記錄寫入暫存表 @re，並標記 level = -1（負值表示尚未確定行進方向）。
2. 同線前進：在同一 lineID 上，依據 flag（+1 正向、-1 反向）尋找下一站，state_count 遞增，line_count 不變。
3. 跨線換乘：在換乘站（current_state 相同但 lineID 不同）發起換乘，line_count +1，並記錄已經過的路線集合 lineIDs，防止重複乘坐同一路線。
4. 方向確定：剛換乘上新路線時 flag = NULL，下一步會嘗試正向（orderid+1）與反向（orderid-1）兩個方向，分別將 flag 設為 1 或 -1，並將 level 轉為正值，表示方向已鎖定。
5. 終止條件：當 current_state = @state_stop 時，將 flag 設為 0，跳出迴圈。

關鍵技術細節

路徑字串編碼

使用 3{1.廣州東->2.體育西->3.珠江新城->4.客村)->2{5.客村->4.中大} 格式：

• 線號{序號.站名 表示進入該路線
• )->線號{ 表示換乘動作
• } 結尾補齊（最終 SELECT 時補加）

防止迴路與重複路線

lineIDs 欄位以 ,1,3,2, 形式記錄已經過路線，換乘前以 CHARINDEX 檢查目標路線是否已在集合中，若存在則略過，確保不重複乘坐同一線路。

OrderID 連續性要求

演算法假設同一路線的 orderid 必須連續（1,2,3…）。若實際資料有斷點（如原始資料 1 號線跳過 5），需先重新編號生成連續序號，再套用演算法。

執行結果解讀

查詢「廣州東」→「中大」可得多條路徑，篩選 line_count（換乘次數+1）與 state_count（途經站數）最小者即為最優方案。範例輸出顯示：

• 方案一：3 號線直達客村 → 換 2 號線至中大（換乘 1 次，5 站）
• 方案二：1 號線至體育西 → 換 3 號線至客村 → 換 2 號線（換乘 2 次，7 站）

效能優化建議

1. 將表變數 @re、@tb 改為暫存表 #re、#tb，於 lineID、state、orderid 建立索引，大幅提升 JOIN 效能。
2. 預先計算 next_orderid = orderid + flag 存入資料表，避免迴圈中重複運算。
3. 若資料量極大，可考慮改用圖資料庫或應用層演算法（Dijkstra/A*）輔助。

總結

純 T-SQL 即可實現複雜的多路線換乘路徑搜尋，關鍵在於狀態機設計（flag、level、lineIDs）與層次擴展邏輯。此方案適合中小型路網、需內嵌於資料庫存儲程序的場景；大型路網建議採用專用圖運算引擎。