1.概述

這兩天，博客園里有人談論到地鐵圖的實現，而之前我也和NeoRAGEx2002同學做了一個Android地鐵圖應用，因此，對于地鐵圖的尋路算法，我覺得有必要專門寫一篇博客來給出我們的解決方案，供大家參考。本文所述算法的時間復雜度為O(|E|log|E|)，其中|E|為邊的數量。

2.概念

1)點和邊

基礎元素為點(地鐵站)和邊(兩個相鄰站之間的有向軌道)。

例如，經過莘莊站有1號線和5號線，含有莘莊站的邊有4條，經過世紀大道站有4條線路，含有世紀大道站的邊有8條。

2)運營段

在邊的基礎上，還有運營段的概念，即一組連續邊的集合。

例如，1號線有莘莊-富錦路(發車間隔8分)、莘莊-上海火車站(發車間隔6分)、上海南站-富錦路(發車間隔8分)、上海南站-上海火車站(發車間隔6分)、富錦路-莘莊(發車間隔8分)、上海火車站-莘莊(發車間隔6分)等運營段。

3)代價

尋路算法的依據可以為時間、換乘次數、經過邊數等任意非負代價，這里著重對時間進行建模。

每條邊有一個乘坐時間代價，表示乘坐地鐵經過該邊所需要花費的時間。

每個運營段有一個等車時間代價，為通過該運營段中的邊乘車需要等車的時間，通常可以假設為發車間隔時間(等車時間的最大值)或者發車間隔時間的一半(等車時間的數學期望)。

在每個點有一個換乘時間代價矩陣，表示在任意兩條邊之間換乘所需要花費的時間。兩邊之間的關系有直接連通、換乘、不連通三種。連通的換乘時間代價為0，換乘的換乘時間代價為換乘行走時間+等車時間，不連通的換乘時間代價為+∞。這個矩陣可以用稀疏矩陣表示，不連通的兩邊不出現。由于地鐵的設計使得我們不需要考慮沿著某條線路折返的路線，我們可以將一邊和它的相反邊看做不連通而不是換乘，這樣可以降低圖的復雜度。

3.算法

1)思路

傳統的最短路徑算法很多，比如

Dijkstra算法，不過這種算法沒有辦法解決換乘時間代價問題。

廣度優先算法，在加權圖的時候無法得到最優解。

受限的深度優先算法，能得到結果，但路徑比較長時算法時間過長。

我們可以考慮這樣一個自然現象，雪水在山峰上融化，然后流經各個山谷。各站點就是山谷中的點，換乘站點就是山谷分成多股的交叉點。

假設起始點是山峰，水沿著各邊擴散，經過一邊的用時和邊上的乘坐時間代價一樣，從一邊到一鄰邊，需要等待換乘時間代價。不停往起始點倒水，水不停流動，當水到達終止點時，水流經過的路徑就是我們所需要的最短路徑。

這個模型的問題在于水可以有多股水流同時流動，但是我們的算法應該有一個順序，我們可以假設有一個水流切線，表示所有水流的最前端位置。任意邊e，當其起點被水流所覆蓋，而終點沒有被水流覆蓋時，將e加入按代價排序的切線邊列表C(紅黑樹或平衡樹實現)，并記錄e->水流經過的上一邊。繼續讓水流動，則C中的第一個邊e的終點最先被水流所覆蓋，從C中移除e。當到達尋路的終止點時，我們可以通過從最后一條邊開始回溯上一邊，再上一邊的上一邊，直到尋路的起點，這樣就獲得了所需要的路徑。

算法也可以不在終點結束，而直到水流覆蓋地圖上的所有點，對性能并沒有明顯的影響。

2)例子

如圖1所示：

　　　　　　　　圖1(a) 時間代價　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　圖1(b) 搜索順序

為了簡化問題，我們假設2號線(綠色)和9號線(水色)不存在，只考慮4號線(深藍色)和6號線(紫紅色)。

圖1(a)中表示了4號線和6號線的邊的時間代價，其中白色表示等車時間，黃色表示乘車時間。

我們假設每個換乘站，換乘時的行走時間為4分鐘。

圖1(b)表示了搜索順序，對于相同的代價，其搜索順序不定，由切線邊列表C的實現決定。

例子中的起始點為世紀大道，終止點為上海兒童醫學中心。

切線邊列表C的變化如下

{1, 2, 3, 5}  
{2, 3, 4, 5}  
{3, 4, 5, 6}  
{4, 5, 6, 9}  
{5, 6, 7, 9}  
{6, 7, 8, 9}  
{7, 8, 9, 10, .., ..}  
{8, 9, 10, .., .., ..}  
{9, 10, .., .., .., ..}  
{10, .., .., .., .., ..} 

需要注意到消去6的時候，增加了10、(藍村路, 塘橋)、9的反向邊三條邊，消去9的時候，增加了6的反向邊。

消去9時，會再次搜索到10，此時的時間代價為13+4+8=25，但因為10已經記錄了其上一邊，所以不再加入C。

#p#

3)實現

偽代碼如下：

record Vertex //點  
    InEdges:List<Edge> //進站邊  
    OutEdges:List<Edge> //出站邊  
    Connection:Map<Tuple<Edge, Edge>, EdgeConnection> //邊連接矩陣，包含換乘行走時間代價，當不連接時不存在  
 
record Edge //邊  
    Start:Vertex //起點  
    End:Vertex //終點  
    Cost:Int //乘坐時間代價  
    Ranges:List<Range> //運營段  
 
record Range //運營段  
    Edges:List<Edge> //邊  
    Cost:Int //等車時間  
 
taggedunion EdgeConnection  
    Connected:Unit //直接連接  
    Transferable:Int //換乘，行走時間代價  
 
CalculateRoute(Start:Vertex, End:Vertex):List<Edge>  
    if Start == End  
        return new List<Edge>() //起始點和終止點重合  
 
    let Previous <- new Map<Edge, Edge>() //邊到上一邊的映射  
    let cmp <- (Comparer<Edge>)(...) //路徑代價比較函數，將在下面給出  
    let CutEdges <- new RedBlackTree<Edge>(cmp) //水流切線邊列表  
 
    foreach o in Start.OutEdges  
        CutEdges <- CutEdges + o  
        Previous <- Previous + (o, null)  
 
    let e <- (Edge)(null) //終邊  
 
    while CutEdges.Count > 0  
        let i <- CutEdges.First  
        CutEdges <- CutEdges - i  
 
        let s <- i.End  
        if s == End  
            e <- i  
            break 
 
        foreach o in s.OutEdges  
            if !s.Connection.ContainsKey((i, o))  
                continue 
 
            if Previous.ContainsKey(o)  
                continue 
 
            Previous <- Previous + (o, i)  
            CutEdges <- CutEdges + o  
 
    if e == null  
        return null //沒有路徑  
 
    let l <- new List<Edge>()  
    while e != null  
        l <- l + e  
        e <- Previous(e)  
 
    return l.Reverse() 

下面為當尋路依據為時間時的比較函數

let Time <- new Map<Edge, Int>()  
let Range <- new Map<Edge, Range>()  
let GetBestRange <- l:List<Range> => l.OrderBy(r => r.Cost).First  
let GetTime <-  
    e =>  
        if e == null  
            return 0  
        if Time.ContainsKey(e)  
            return Time(e)  
        let p <- Previous(e)  
        let v <- GetTime(p)  
        if p != null  
            let c <- e.Start.Connection((p, e))  
            if c  
            | Connected ->  
                let rgOld <- Range(p)  
                let rg <- GetBestRange(p.Ranges.Intersect(e.Ranges))  
                Range <- Range + (e, rg)  
                if rgOld != rg  
                    v <- v - rgOld.Cost + rg.Cost  
            | Transferable t ->  
                let rg <- GetBestRange(e.Ranges)  
                Range <- Range + (e, rg)  
                v <- v + rg.Cost + t  
        else 
            let rg <- GetBestRange(e.Ranges)  
            Range <- Range + (e, rg)  
            v <- v + rg.Cost  
        v <- v + e.Cost  
        Time <- Time + (e, v)  
        return v  
let cmp <-  
    (l:Edge, r:Edge) =>  
        return GetTime(l) - GetTime(r) 

下面為當尋路依據為換乘次數時的比較函數

let TransferCount <- new Map<Edge, Int>()  
let GetTransferCount <-  
    e =>  
        if e == null  
            return 0  
        if TransferCount.ContainsKey(e)  
            return TransferCount(e)  
        let p <- Previous(e)  
        let v <- GetTransferCount(p)  
        if p != null  
            let c <- e.Start.Connection((p, e))  
            if c  
            | Connected ->  
                ()  
            | Transferable _ ->  
                v += 1  
        TransferCount <- TransferCount + (e, v)  
        return v  
let cmp <-  
    (l:Edge, r:Edge) =>  
        return GetTransferCount(l) - GetTransferCount(r) 

下面為當尋路依據為經過邊數時的比較函數
 

let StopCount <- new Map<Edge, Int>()  
let GetStopCount <-  
    e =>  
        if e == null  
            return 0  
        if StopCount.ContainsKey(e)  
            return StopCount(e)  
        let p <- Previous(e)  
        let v <- GetStopCount(p) + 1  
        StopCount <- StopCount + (e, v)  
        return v  
let cmp <-  
    (l:Edge, r:Edge) =>  
        return GetStopCount(l) - GetStopCount(r) 

4.算法復雜度

認為點的入站邊和出站邊很少，覆蓋每條邊的運營段很少，并注意到GetTime運行時遞歸的部分總會在Time變量中緩存，可知時間比較函數的復雜度為O(1)。

CutEdges的紅黑樹插入刪除的復雜度為O(log|E|)。

所有邊最多進出CutEdges一次，可知整個算法的復雜度為O(|E|log|E|)。

5.結果

本文所述算法能夠在O(|E|log|E|)時間內快速得到全局最佳路徑。

在1GHz的單CPU手機上實測得到的上海地鐵(11條線路214站)任意兩站點之間的尋路時間均為200ms以下。

最后還是介紹下我們的應用。

矢量地鐵（上海版）

支持雙指無極縮放、動態尋徑效果、本地地圖顯示。雖然我們只是一個小團隊，但我們只做最好的地鐵圖！如果大家有啥問題和建議，歡迎給我們留言！

原文鏈接：http://www.cnblogs.com/Rex/archive/2012/08/12/2634401.html