Path

程度★ 難度★

「圖」與「道路地圖」

把一張圖想像成道路地圖,把圖上的點想像成地點,把圖上的邊想像成道路,把權重想像成道路的長度。若兩點之間以邊相連,表示兩個地點之間有一條道路,道路的長度是邊的權重。

有時候為了應付特殊情況,邊的權重可以是零或者負數,也不必真正照著圖上各點的地理位置來計算權重。別忘記「圖」是用來記錄關聯的東西,並不是真正的地圖。

Path

在圖上任取兩點,分別作為起點和終點,我們可以規劃許多條由起點到終點的路線。不會來來回回繞圈子、不會重覆經過同一個點和同一條邊的路線,就是一條「路徑」。

如果起點到終點是不通的,那麼就不存在起點到終點的路徑。如果起點和終點一樣,那麼就存在路徑,路徑是一個點、零條邊。

路徑也有權重。路徑經過的每一條邊,沿路加總權重,就是路徑的權重(通常只加總邊的權重,而不考慮點的權重)。路徑的權重,可以想像成路徑的總長度。

Shortest Path

程度★ 難度★★

Shortest Path

「最短路徑」是由起點到終點、權重最小的路徑,可能有許多條,也可能不存在。起點到終點不通、不存在路徑的時候,就沒有最短路徑。

「最短路徑」不見得是邊最少、點最少的路徑。

最短路徑是NP-complete問題;當圖上確定沒有負環,才是P問題。「負環Negative Cycle」是權重為負值的環。

Longest Path

最長路徑和最短路徑很類似。最長路徑問題當中,每一條邊的權重添上負號,就變成最短路徑問題。反過來也是。

最長路徑是NP-complete問題;當圖上確定沒有正環,才是P問題。

Shortest Path Tree

最短路徑有一個特別的性質:每一條最短路徑,都是由其它的最短路徑延展而得。一條最短路徑,截去末端之後,還是最短路徑。

提到延展,就聯想到樹!引入延展的概念,最短路徑們得以形成一棵樹。

在圖上選定一個起點,由起點到圖上各點的最短路徑們,形成一棵有向樹,稱作「最短路徑樹」。由於兩點之間的最短路徑不見得只有一條,所以最短路徑樹也不見得只有一種。

Shortest Path Graph【尚無正式稱呼】

在圖上選定一個起點和一個終點,由起點到終點的所有最短路徑們,形成一張有向圖,稱作「最短路徑圖」,只有唯一一種。

當圖上每一條邊的權重都是正數,最短路徑圖是有向無環圖(Directed Acyclic Graph, DAG)。

兩點之間有多條邊

當一張圖的兩點之間有多條邊,可以留下一條權重最小的邊。這麼做不影響最短路徑。

當圖的資料結構為adjacency matrix,任兩點之間只能擁有一個權重值。此時權重值必須設定成權重最小的邊的權重。

兩點之間沒有邊(兩點不相鄰)

當一張圖的兩點之間沒有邊,可以補上一條權重無限大的邊。這麼做不影響最短路徑。

當圖的資料結構為adjacency matrix,任兩點之間一定要有一個權重值。此時權重值必須設定成一個超大數字,當作無限大;不可設定為零,以免計算錯誤。

最短路徑長度無限大、負無限大

當起點無法到達終點,就沒有最短路徑了。這種情況常被解讀成:起點永遠走不到終點,導致最短路徑長度無限大。

最短路徑的長度不可能是負無限大。最短路徑的點和邊不能重複,無法藉由負邊、負環讓長度不斷減少。

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的概念。

演算法

一、將起點加入到最短路徑樹。此時最短路徑樹只有起點。
二、重複下面這件事V-1次,將剩餘所有點加入到最短路徑樹。
 甲、尋找一個目前不在最短路徑樹上而且離起點最近的點b。
 乙、將b點加入到最短路徑樹。

運用Memoization,建立表格紀錄最短路徑長度,便容易求得不在樹上、離根最近的點。時間複雜度是O(V^3)。

令w[a][b]是a點到b點的距離(即是邊的權重)。
令d[a]是起點到a點的最短路徑長度,起點設為零,其他點都是空的。

一、將起點加入到最短路徑樹。此時最短路徑樹只有起點。
二、重複下面這件事V-1次,將剩餘所有點加入到最短路徑樹。
 甲、尋找一個目前不在最短路徑樹上而且離起點最近的點:
   以窮舉方式,
   找一個已在最短路徑樹上的點a,以及一個不在最短路徑樹上的點b,
   讓d[a]+w[a][b]最小。
 乙、將b點的最短路徑長度存入到d[b]之中。
 丙、將b點(連同邊ab)加入到最短路徑樹。

實作

Graph Traversal

Label Setting Algorithm亦可看作是一種Graph Traversal,遍歷順序是先拜訪離樹根最近的點和邊。

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^2)。

甲乙相加就是整體的時間複雜度。圖的資料結構為adjacency matrix的話,便是O(V^2);圖的資料結構為adjacency lists的話,還是O(V^2)。

實作

延伸閱讀:Fibonacci Heap

用特殊的資料結構可以加快這個演算法。建立V個元素的Fibonacci Heap,用其decrease key函式來實作relaxation,用其extract min函式來找出下一個點,可將時間複雜度降至O(E+VlogV)。

UVa 10801 10841 10278 10187 10039

Single Source Shortest Paths: Label Setting Algorithm + Priority Queue

程度★★ 難度★

演算法

找不在樹上、離根最近的點,先前的方式是:窮舉樹上a點及非樹上b點,也就是窮舉從樹上到非樹上的邊ab,以找出最小的d[a]+w[a][b]。

現在把d[a]+w[a][b]的值通通倒進Priority Queue。找不在樹上、離根最近的點,就從Priority Queue取出邊(與點);每次relaxation就將邊(與點)塞入Priority Queue。

學過State Space Search的讀者,可以發現此演算法正是Uniform-cost Search,因此也有人說此演算法是考慮權重的BFS。

時間複雜度:維護Priority Queue

首先必須確認Priority Queue的大小。圖上每一條邊皆用於relaxation一次,所以Priority Queue前前後後一共塞入了E條邊,最多也只能取出E條邊。Priority Queue的大小為O(E)。

塞入一條邊皆需時O(logE),塞入E條邊皆需時O(ElogE)。取出亦如是。由此可知維護Priority Queue需時O(ElogE)。

在最短路徑問題當中,如果兩點之間有多條邊,只要取權重比較小的邊來進行最短路徑演算法就行了。也就是說,兩點之間只會剩下一條邊。也就是說,邊的總數不會超過C{V,2} = V*(V-1)/2個。也就是說,上述的時間複雜度O(ElogE),得改寫成O(Elog(V^2)) = O(2ElogV) = O(ElogV)。

Priority Queue可以採用Binary Heap或Binomial Heap,時間複雜度都相同。

當圖上每條邊的權重皆為正整數的情況下,Priority Queue亦得採用vEB Tree,時間複雜度下降成O(EloglogW),其中W為最長的最短路徑長度。

時間複雜度

一次Graph Traversal的時間,加上維護Priority Queue的時間。

圖的資料結構為adjacency matrix的話,便是O(V^2 + ElogE);圖的資料結構為adjacency lists的話,便是O(V+E + ElogE)。

這個方法適用於圖上的邊非常少的情況。若是一般情況,使用Dijkstra's Algorithm會比較有效率,程式碼的結構也比較簡單。

Single Source Shortest Paths: Dijkstra's Algorithm + Priority Queue

程度★★ 難度★

演算法

時間複雜度與上一篇文章相同,然而效率較佳。

令w[a][b]是a點到b點的距離(即是邊的權重)。
令d[a]是起點到a點的最短路徑長度,起點設為零,其他點都是空的。
令PQ是一個存放點的Priority Queue,由小到大排序鍵值。

一、把起點放入PQ。
二、重複下面這件事,直到最短路徑樹完成為止:
 甲、嘗試從PQ中取出一點a,點a必須是目前不在最短路徑樹上的點。
 乙、將a點(連同其邊)加入最短路徑樹。
 丙、將所有與a點相鄰且不在樹上的點的點b(連同邊ab)放入PQ,
   設定鍵值為d[a] + w[a][b],鍵值同時也存入d[b],
   但是會先檢查d[a] + w[a][b]是不是小於d[b],
   小於才放入PQ,鍵值才存入d[b]。
   (此步驟即是以邊ab進行ralaxation。)

UVa 10278 10740 10986

Single Source Shortest Paths: Dial's Algorithm

程度★★ 難度★

演算法

用Bucket Sort代替表格,把d[a]+w[a][b]的值通通拿去做Bucket Sort。用在每條邊的權重都是非負整數的圖。

時間複雜度:進行Bucket Sort

整個bucket最多放入E個點、拿出E個點,然後整個bucket讀過一遍,時間複雜度總共是O(E+W),其中W為bucket的數目,也是最長的最短路徑長度。

當圖上每條邊的權重不是整數時,時間複雜度是O(WV)。

時間複雜度

一次Graph Traversal的時間,再加上Bucket Sort的時間。

圖的資料結構為adjacency matrix的話,便是O(V^2 + W);圖的資料結構為adjacency lists的話,便是O(V+E + W)。

當圖上每條邊的權重不是整數時。圖的資料結構為adjacency matrix的話,便是O(V^2 + WV);圖的資料結構為adjacency lists的話,便是O(V+E + WV)。

Single Source Shortest Paths: Gabow's Algorithm

程度★★ 難度★★★

用途

一張有向圖,選定一個起點,找出起點到圖上各點的最短路徑,即是找出其中一棵最短路徑樹。但是限制是:圖上每一條邊的權重皆非負整數。

演算法

採用Scaling Method。詳細內容可參考CLRS習題24-4,此處僅略述。

重複以下步驟O(logC)次,每個步驟要求出當下的最短路徑:
一、令權重更加精細。
二、以上一步驟算得的最短路徑長度來調整權重。
  並以調整後的權重求最短路徑,可用O(V+E)時間求得。
  (調整過的權重剛好皆為非負數,且最短路徑長度都不會超過E。)
三、還原成正確的最短路徑長度。

Scaling Method的精髓,在於每次增加精細度後,必須有效率的修正前次與今次的誤差。此演算法巧妙運用調整權重的技術,確切找出前次與今次差異之處,而得以用O(E)時間修正誤差。

上述O(V+E)求最短路徑的演算法,仍是運用Dijkstra's Algorithm「最近的點先找」概念,只是求法有點小改變。首先開個E+1條linked list,離起點距離為x的點,就放在第x條。只要依序掃描一遍所有的linked list,就可以求出最短路徑了。

時間複雜度

整個演算法總共O(logC)個步驟,C是整張圖權重最大的邊的權重。

圖的資料結構為adjacency matrix的話,每一步驟需要O(V^2)時間,整體時間複雜度為O(V^2 * logC);圖的資料結構為adjacency lists的話,每一步驟需要O(V+E)時間(簡單記為O(E)),整體時間複雜度為O(ElogC)。

找出一棵最短路徑樹(adjacency lists)

【待補程式碼】