path
路漫漫其修遠兮,吾將上下而求索。《屈原.離騷》
「圖」與「道路地圖」
一張圖想像成道路地圖,點想像成地點,邊想像成道路,權重想像成道路的長度。若兩點之間以邊相連,表示兩個地點之間有一條道路,道路的長度是邊的權重。
有時候為了應付特殊情況,邊的權重可以是零或者負數,也不必真正照著圖上各點的地理位置來計算權重。別忘記「圖」是用來記錄關聯的東西,並不是真正的地圖。
path
在圖上任取兩點,分別作為起點和終點,我們可以規劃許多條由起點到終點的路線。一條路線就是一條「路徑」。
如果起點到終點是不通的,那麼就不存在起點到終點的路徑。如果起點和終點一樣,那麼就存在路徑,路徑是一個點、零條邊。
路徑也有權重。路徑經過的每一條邊,沿路加總權重,就是路徑的權重(通常只加總邊的權重,而不考慮點的權重)。路徑的權重,可以想像成路徑的總長度。
shortest path
shortest path
「最短路徑」是由起點到終點、權重最小的路徑,可能有許多條,也可能不存在。起點到終點不通、不存在路徑的時候,就沒有最短路徑。
「最短路徑」不見得是邊最少、點最少的路徑。
longest path
最長路徑和最短路徑很類似。最長路徑問題當中,每一條邊的權重添上負號,就變成最短路徑問題。反過來也是。
shortest-path tree
最短路徑有一個特別的性質:每一條最短路徑,都是由其它的最短路徑延展而得。一條最短路徑,截去末端之後,還是最短路徑。
提到延展,就聯想到樹!引入延展的概念,最短路徑們得以形成一棵樹。
在圖上選定一個起點,由起點到圖上各點的最短路徑們,形成一棵有向樹,稱作「最短路徑樹」。由於兩點之間的最短路徑不見得只有一條,所以最短路徑樹也不見得只有一種。
shortest-path graph
在圖上選定一個起點和一個終點,由起點到終點的所有最短路徑們,形成一張有向圖,稱作「最短路徑圖」,只有唯一一種。
當圖上每一條邊的權重都是正數,最短路徑圖是有向無環圖DAG。
兩點之間有多條邊
當一張圖的兩點之間有多條邊,可以留下一條權重最小的邊。這麼做不影響最短路徑。
當圖的資料結構為adjacency matrix,任兩點之間只能擁有一個權重值。此時權重值必須設定成權重最小的邊的權重。
兩點之間沒有邊(兩點不相鄰)
當一張圖的兩點之間沒有邊,可以補上一條權重無限大的邊。這麼做不影響最短路徑。
當圖的資料結構為adjacency matrix,任兩點之間一定要有一個權重值。此時權重值必須設定成一個超大數字,當作無限大;不可設定為零,以免計算錯誤。
最短路徑長度正無限大、負無限大
當起點無法到達終點,就沒有最短路徑了。這種情況常被解讀成:起點永遠走不到終點,導致最短路徑長度正無限大。
當起點到終點之間存在負邊、負環,不斷折返負邊、不斷繞行負環,導致最短路徑的長度負無限大。
「負邊negative edge」是權重為負值的邊。「負環negative cycle」是權重為負值的環。
relaxation
最後介紹最短路徑演算法一個共通的重要概念「鬆弛」。
尋找兩點之間的最短路徑時,最直觀的方式莫過於:先找一條路徑,然後再找其他路徑,看看會不會更短,並記住最短的一條。
找更短的路徑並不困難。我們可以尋覓捷徑,以縮短路徑;也可以另闢蹊徑,取代原本的路徑。如此找下去,必會找到最短路徑。
尋覓捷徑、另闢蹊徑的過程,可以以數學方式來描述:現在要找尋起點為s、終點為t的最短路徑,而且現在已經有一條由s到t的路徑,這條路徑上會依序經過a及b這兩點(可以是起點和終點)。我們可以找到一條新的捷徑,起點是a、終點是b的捷徑,以這條捷徑取代原本由a到b的這一小段路徑,讓路徑變短。
找到捷徑以縮短原本路徑,便是relaxation。
最短路徑演算法的功能類型
point-to-point shortest path,點到點最短路徑: 給定起點、終點,求出起點到終點的最短路徑。一對一。 single source shortest paths,單源最短路徑: 給定起點,求出起點到圖上每一點的最短路徑。一對全。 all pairs shortest paths,全點對最短路徑: 求出圖上所有兩點之間的最短路徑。全對全。
最短路徑演算法的原理
label setting: 逐步設定每個點的最短路徑長度,一旦設定後就不再更改。 負邊不適用。 label correcting: 設定某個點的最短路徑長度之後,之後仍可繼續修正,越修越美。 整個過程就是不斷重新標記每個點的最短路徑長度。 負邊適用。
single source shortest paths: label setting algorithm
用途
一張有向圖,選定一個起點,找出起點到圖上各點的最短路徑。即是找出其中一棵最短路徑樹。
限制是:圖上每一條邊的權重皆非負數。
想法
當圖上每一條邊的權重皆非負數時,可以發現:每一條最短路徑,都是邊數更少、權重更小(也可能相同)的最短路徑的延伸。
於是乎,建立最短路徑樹,可以從邊數最少、權重最小的最短路徑開始建立,然後逐步延伸拓展。換句話說,就是從距離起點最近的點和邊開始找起,然後逐步延伸拓展。先找到的點和邊,保證會是最短路徑樹上的點和邊。
也可以想成是,從目前形成的最短路徑樹之外,屢次找一個離起點最近的點,(連帶著邊)加入到最短路徑樹之中,直到圖上所有點都被加入為止。
整個演算法的過程,可看作是兩個集合此消彼長。不在樹上、離根最近的點,移之。
運用已知的最短路徑,求出其他的最短路徑。循序漸進、保證最佳,這是greedy method的概念。
整個演算法的過程,亦可看作是一種特殊的graph traversal,遍歷順序是優先拜訪離樹根最近的點和邊。
演算法
一、將起點加入到最短路徑樹。此時最短路徑樹只有起點。 二、重複下面這件事V-1次,將剩餘所有點加入到最短路徑樹。 甲、尋找一個目前不在最短路徑樹上而且離起點最近的點b。 乙、將b點加入到最短路徑樹。
運用memoization,建立表格記錄最短路徑長度,便容易求得不在樹上、離根最近的點。時間複雜度O(V³)。
令w[a][b]是a點到b點的距離(即是邊的權重)。 令d[a]是起點到a點的最短路徑長度,起點設為零,其他點都是空的。 一、將起點加入到最短路徑樹。此時最短路徑樹只有起點。 二、重複下面這件事V-1次,將剩餘所有點加入到最短路徑樹。 甲、尋找一個目前不在最短路徑樹上而且離起點最近的點: 以窮舉方式, 找一個已在最短路徑樹上的點a,以及一個不在最短路徑樹上的點b, 讓d[a]+w[a][b]最小。 乙、將b點的最短路徑長度存入到d[b]之中。 丙、將b點(連同邊ab)加入到最短路徑樹。
實作
parent[]用來找出最短路徑。
single source shortest paths: Dijkstra's algorithm
想法
找不在樹上、離根最近的點,先前的方式是:窮舉樹上a點及非樹上b點,找出最小的d[a]+w[a][b]。整個過程重覆窮舉許多邊。
表格改為儲存d[a]+w[a][b],就不必重覆窮舉邊了。每當一個a點加入最短路徑樹,就將d[a]+w[a][b]存入d[b]。找不在樹上、離根最近的點,就直接窮舉d[]表格,找出最小的d[b]。
演算法
令w[a][b]是a點到b點的距離(即是邊的權重)。 令d[a]是起點到a點的最短路徑長度,起點設為零,其他點都設為無限大。 一、重複下面這件事V次,以將所有點加入到最短路徑樹。 甲、尋找一個目前不在最短路徑樹上而且離起點最近的點: 直接搜尋d[]陣列裡頭的數值,來判斷離起點最近的點。 乙、將此點加入到最短路徑樹之中。 丙、令剛剛加入的點為a點, 以窮舉方式,找一個不在最短路徑樹上、且與a點相鄰的點b, 把d[a]+w[a][b]存入到d[b]當中。 因為要找最短路徑,所以儘可能記錄越小的d[a]+w[a][b]。 (即是邊ab進行relaxation)
以relaxation的觀點來看,此演算法不斷以邊ab作為捷徑,讓起點到b點的路徑長度縮短為d[a]+w[a][b]。
時間複雜度
一、加入點、窮舉邊:每個點只加入一次,每條邊只窮舉一次,剛好等同於一次graph traversal的時間。
二、尋找下一個點:從大小為V的陣列當中尋找最小值,O(V);總共尋找了V次,O(V²)。
圖的資料結構為adjacency matrix是O(V²);圖的資料結構為adjacency lists仍是O(V²)。
實作
UVa 10801 10841 10278 10187 10039
single source shortest paths: label setting algorithm with priority queue
演算法
d[a]+w[a][b]通通倒進priority queue。
找不在樹上、離根最近的點:從Priority queue彈出邊(與點)。
relaxation:將邊(與點)塞入priority queue。
時間複雜度:維護priority queue
圖上每一條邊皆用於relaxation一次,因此priority queue前前後後一共塞入E條邊、頂多彈出E條邊。priority queue的大小是O(E)。
priority queue實務上習慣採用binary heap。塞入一條邊皆需時O(logE),塞入E條邊皆需時O(ElogE)。彈出亦然。維護priority queue需時O(ElogE)。
在最短路徑問題當中,如果兩點之間有多條邊,只要取權重最小的邊來進行最短路徑演算法就行了。預先以O(V+E)時間掃描一次所有邊,保留權重最小的邊。也就是說,兩點之間只會剩下一條邊。也就是說,邊數至多C(V,2) = V(V-1)/2 = O(V²)條。也就是說,時間複雜度O(ElogE)可以改寫成O(ElogV²) = O(2ElogV) = O(ElogV)。
時間複雜度
一次graph traversal的時間,加上維護priority queue的時間。
圖的資料結構為adjacency matrix是O(V² + ElogV);圖的資料結構為adjacency lists是O(V+E + ElogV) = O(V + ElogV)。
這個演算法適用於邊數非常少的情況。
實作
single source shortest paths: Dijkstra's algorithm with priority queue
演算法
d[a]+w[a][b],既存入d[]表格,也塞入priority queue。
找不在樹上、離根最近的點:不再窮舉d[]表格,改為從priority queue彈出。
relaxation:先檢查d[]表格,才塞入priority queue。
時間複雜度跟上個章節相同,但是效率更好。
延伸閱讀:特殊的priority queue
運用特殊的資料結構可以降低時間複雜度。僅有理論上的價值,沒有實務上的價值。
建立V個元素的Fibonacci heap,用其decrease key函式來實作relaxation,用其extract min函式來找出下一個點,時間複雜度降為 O(V+E + VlogV) = O(E + VlogV)。
當圖上每條邊的權重皆為正整數,採用vEB tree,時間複雜度降為O(V+E + EloglogL) = O(V + EloglogL),L是最長路徑長度。
實作
UVa 10278 10740 10986
single source shortest paths: Dial's algorithm
演算法
當權重不是整數,d[a]+w[a][b]通通拿去做bucket sort。
當權重都是整數,d[a]+w[a][b]通通拿去做counting sort。
時間複雜度:bucket sort
一、桶子們最多塞入E次、彈出E次。O(E)。
二、桶子們讀過一遍。O(L)。
當權重不是整數,時間複雜度O(ElogE + L)。
當權重都是整數,時間複雜度O(E+L)。
L是桶子數目,頂多是最長路徑長度、再加一。
時間複雜度
一次graph traversal的時間,加上bucket sort的時間。
當權重都是整數,圖的資料結構為adjacency matrix是O(V² + L);圖的資料結構為adjacency lists是O(V+E+L)。
這個演算法適用於路徑普遍很短的情況。
實作:權重都是整數
single source shortest paths: Gabow's algorithm
用途
限制是:圖上每一條邊的權重皆非負數、皆是整數。
演算法
scaling method,權重精度逐步上升。
權重視作二進位數字,從最高數量級開始,每回合添加一個位數,並且修正上回合與本回合的答案誤差。
重複以下步驟,每回合都求出當下的最短路徑: 一、每條邊權重翻倍:上回合的最短路徑長度隨著翻倍。 二、每條邊權重加零或加一:修正最短路徑長度的誤差。 甲、調整權重:扣除上回合的最短路徑長度的兩倍。《Johnson's algorithm》 乙、調整後的權重,求最短路徑長度。《Dial's algorithm》 (調整後的權重皆非負數,最短路徑長度至多是E。) 丙、還原權重:補足上回合的最短路徑長度的兩倍。 得到本回合的最短路徑長度。
權重加倍,不影響最短路徑位置。最短路徑長度隨著翻倍。
權重加零或加一,整張圖頂多增加E條邊、權重為1。最差情況是全部聚集於同一條最短路徑,最短路徑長度頂多增加E。
調整權重之後,最短路徑長度頂多是E,只需要E+1個桶子。
時間複雜度
總共O(logW)回合。W是最大的邊權重。
舉例來說,unsigned int總共32個位元,總共32回合。int非負數部分總共31個位元,總共31回合。
圖的資料結構為adjacency matrix是((V² + E)logW);圖的資料結構為adjacency lists是O((V+E)logW)。