Path

「圖」與「道路地圖」

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

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

Path

在圖上任取兩點,分別做為起點和終點,我們可以規劃出許多條由起點到終點的路線。這些路線可以經過其他點,也可以來來回回的繞圈子。一條路線,就是一條「路徑」。

如果起點到終點是不相通的,那麼就不會存在起點到終點的路徑。

路徑也有權重。把路徑上所有邊的權重,都加總起來,就是路徑的權重(通常只加總邊的權重,而不考慮點的權重)。路徑的權重,可以想像成路徑的總長度。

一條路徑,如果沒有重複地經過同樣的點,則稱做「簡單路徑」。

【註:一般情況下,當我們說「路徑」時,可以是指「簡單路徑」──這是因為「重覆地經過同樣的點的路徑」比較少用,而「簡單路徑」四個字又不如「路徑」兩個字來的簡潔。因此很多專有名詞便省略了「簡單」這兩個字,而直接使用「路徑」,但實際上是指「簡單路徑」。】

Cycle

既然講了路徑,就順便介紹一下「環」。一條路徑的起點與終點是同一點,便稱之為一只環。

一只環,除了起點之外,如果沒有重複地經過同樣的點,則稱做「簡單環」。

Shortest Path

「最短路徑」。在一張權重圖上,兩點之間權重最小的路徑。

Longest Path

「最長路徑」。在一張權重圖上,兩點之間權重最大的簡單路徑。已被證明是NP-Complete問題。

Shortest Path

Shortest Path

「最短路徑」,在一張權重圖上,兩點之間權重最小的路徑。最短路徑不見得是邊最少、點最少的路徑。

最短路徑也可能不存在。兩點之間不連通、不存在路徑的時候,也就不會有最短路徑了。

Relaxation

尋找兩點之間的最短路徑時,最直觀的方式莫過於:先找一條路徑,然後再找其他路徑,看看會不會更短,並記住最短的一條。

找更短的路徑並不困難。我們可以在一條路徑上找出捷徑,以縮短路徑;也可以另闢蹊徑,取代原本的路徑。如此找下去,必會找到最短路徑。

尋找捷徑、另闢蹊徑的過程,可以以數學方式來描述:現在要找尋起點為s、終點為t的最短路徑,而且現在已經有一條由s到t的路徑,這條路徑上會依序經過a及b這兩點(可以是起點和終點)。我們可以找到一條新的捷徑,起點是a、終點是b的捷徑,以這條捷徑取代原本由a到b的這一小段路徑,讓路徑變短。

找到捷徑以縮短原本路徑,便是Relaxation。

Negative Cycle

權重為負值的環。以下簡稱負環。

有一種情形會讓最短路徑成為無限短:如果一張圖上面有負環,那麼只要建立一條經過負環的捷徑,便會讓路徑縮短一些;只要不斷地建立經過負環的捷徑,反覆地繞行負環,那麼路徑就會可以無限的縮短下去,成為無限短。

大部分的最短路徑演算法都可以偵測出圖上是否有負環,不過有些卻不行。

無限長與無限短

當起點和終點之間不存在路徑的時候,也就不會有最短路徑了。這種情況有時候會被解讀成:從起點永遠走不到終點,所以最短路徑無限長。

當圖上有負環可做為捷徑的時候,這種情況則是:最短路徑無限短。

最短路徑都是簡單路徑

除了負環以外,如果一條路徑重複的經過同一條邊、同一個點,一定會讓路徑長度變長。由此可知:沒有負環的情況下,最短路徑都是簡單路徑,決不會經過同樣的點兩次,也決不會經過同樣的邊兩次。

Shortest Path Tree

當一張圖沒有負環時,在圖上選定一個點做為起點,由此起點到圖上各點的最短路徑們,會延展成一棵樹,稱作「最短路徑樹」。由於最短路徑不見得只有一條,以特定一點做為起點的最短路徑樹也不見得只有一種。

最短路徑樹上的每一條最短路徑,都是由其它的最短路徑延伸拓展而得(除了由起點到起點這一條最短路徑以外)。也就是說,最短路徑樹上的每一條最短路徑,都是以其他的最短路徑做為捷徑。

當兩點之間有多條邊

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

當兩點之間沒有邊

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

當圖的資料結構為adjacency matrix時,任兩點之間都一定要有一個權重值。要找最短路徑,不相鄰的兩點必須設定權重無限大,而不能使用零,以免計算錯誤;要找最長路徑,則是要設定權重無限小。

Single Source Shortest Paths:
Label Setting Algorithm

總論

最短路徑演算法,可分為兩大類別:Label Setting Algorithm和Label Correcting Algorithm。所謂Label,就是在圖上的點(或邊)標記數值或符號:http://mathworld.wolfram.com/LabeledGraph.html

歸類為Label Setting Algorithm的最短路徑演算法,是逐步設定每個點的最短路徑長度值,一旦設定後就不再更改。

歸類為Label Correcting Algorithm的最短路徑演算法,則是設定某個點的最短路徑長度值之後,之後仍可繼續修正其值,越修越美。整個過程就是不斷重新標記每個點的最短路徑長度值。

用途

選定一個起點後,Label Setting Algorithm可以求出此點到圖上各點的最短路徑,即是最短路徑樹。但是限制是:圖上每一條邊的權重皆非負數。

演算法

當圖上每一條邊的權重皆非負數時,可以發現:每一條最短路徑,都是邊數更少、權重更小(也可能相同)的最短路徑的延伸。

於是乎,建立最短路徑樹,可以從邊數較少的最短路徑開始建立,然後逐步延伸拓展。換句話說,就是從距離起點最近的點和邊開始找起,然後逐步延伸拓展。先找到的點和邊,保證會是最短路徑樹上的點和邊。

也可以想成是,從目前形成的最短路徑樹之外,屢次找一個離起點最近的點,(連帶著邊)加入到最短路徑樹之中,直到圖上所有點都被加入為止。

整個演算法的過程,可看作是兩個集合此消彼長。不在樹上、離根最近的點,移之。

循序漸進、保證最佳,這是Greedy Method的概念。

一點到多點的最短路徑、求出最短路徑樹

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

這裡提供一個簡單的實作。運用Memoization,建立表格紀錄已求得的最短路徑長度,便容易求得不在樹上、離根最近的點。時間複雜度是O(V^3)。

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

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

換個角度看事情

前面有提到relaxtion的概念。以捷徑的觀點來看,當下已求得的每一條最短路徑,都會作為捷徑,縮短所有由起點到圖上各點的路徑。每個步驟中所得到的最短路徑,由於比它更短的最短路徑全都嘗試做為捷徑過了,所以能夠確保是最短路徑。

Label Setting Algorithm亦可看做是一種Graph Traversal,但與BFS和DFS不同的地方在於Label Setting Algorithm有考慮權重,遍歷順序是先拜訪離樹根最近的點和邊。

Single Source Shortest Paths:
Dijkstra's Algorithm

用途

請參考Label Setting Algorithm的說明。

演算法

Label Setting Algorithm的變化版本。

前面介紹的Label Setting Algorithm,找不在樹上、離根最近的點,是窮舉樹上a點及非樹上b點,找出最小的w[a]+d[a][b]。

Dijkstra's Algorithm做了一個小改進,把全部的w[a]+d[a][b]先行存入d[b]中,然後直接窮舉d[]表格,找出最小的d[b]。

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

1. 重複下面這件事V次,以將所有點加入到最短路徑樹。
 甲、尋找一個目前不在最短路徑樹上而且離起點最近的點:
   直接搜尋d[]陣列裡頭的數值,來判斷離起點最近的點。
 乙、將此點加入到最短路徑樹之中。
 丙、以窮舉方式,
   找一個已在最短路徑樹上的點a,以及一個不在最短路徑樹上的點b,
   把d[a]+w[a][b]存入到d[b]當中,
   d[a]+w[a][b]比d[b]小,則有存入的意義,因為要找最短路徑。
   (此步驟即是以邊ab進行ralaxation。)

上面這個演算法仍是O(V^3)。接下來還有一個更重要的改進,每當將a點加入最短路徑樹,只窮舉與a點相鄰的b點,並將w[a]+d[a][b]存入d[b]中。本來需要窮舉樹上所有點,現在不必了。

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

1. 重複下面這件事V次,以將所有點加入到最短路徑樹。
 甲、尋找一個目前不在最短路徑樹上而且離起點最近的點:
   直接搜尋d[]陣列裡頭的數值,來判斷離起點最近的點。
 乙、將此點加入到最短路徑樹之中。
 丙、令剛剛加入的點為a點,
   以窮舉方式,找一個不在最短路徑樹上(且與a點相鄰)的點b,
   把d[a]+w[a][b]存入到d[b]當中,
   d[a]+w[a][b]比d[b]小,則有存入的意義,因為要找最短路徑。
   (此步驟即是以邊ab進行ralaxation。)

經過第一次改進後,一樣的(a,b)之下,其w[a]+d[a][b]會存入表格很多次。經過第二次改進後,一種(a,b)之下,其w[a]+d[a][b]只會存入表格一次。

時間複雜度

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

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

換個角度看事情

一條比較長的最短路徑,移除尾端一小段後,就變成了一條比較短的最短路徑。有分割問題的味道。利用這一點,我們可以製造出遞迴公式,並利用Dynamic Programming解題。Dijkstra's Algorithm可以看做是bottom-up、往後補值的DP。

UVa 10801 10841 10278 10187 10039

Single Source Shortest Paths:
Label Setting Algorithm + Priority Queue

用途

請參考Label Setting Algorithm的說明。

演算法

Label Setting Algorithm的變化版本。找不在樹上、離根最近的點,也可以直接把w[a]+d[a][b]的值通通倒進Priority Queue。

每次要尋找一個離起點最近的點,就直接從Priority Queue拿出一個最近的點;每次relaxation,就把更新過的點塞入Priority Queue。

這裡提供一種實作。讀過State Space Search這個章節的讀者,可發現這個實作便是Uniform-cost Search,因此也有人說這個實作是考慮權重的BFS。

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

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

這裡提供一種更好的實作,是Dijkstra's Algorithm加上Priority Queue。

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

1. 把起點放入PQ。
2. 重複下面這件事,直到最短路徑樹完成為止:
 甲、嘗試從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。)

時間複雜度:操作Priority Queue

分為兩種情形討論。

一、將點放入Priority Queue的時間:

首先要確定Priority Queue的大小才行。根據先前的說明,可以發現Priority Queue裡頭全部都是經過relaxation之後的點。以邊的觀點來思考,圖上的每條邊剛好都會用於relaxation一次,一條邊對應一個塞入Priority Queue的點,所以Priority Queue前前後後一共塞入了E個點,大小為O(E)。

所以,塞入一個點到Priority Queue需時O(logE),前前後後一共塞入了E個點,所以維護Priority Queue的時間為O(ElogE)。

二、將點拿出Priority Queue的時間:

要建立最短路徑樹,只要從Priority Queue取出V個點即可。取出一個點需時O(logE),故取出V個點需時O(VlogE)。

綜合第一點和第二點,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會比較有效率,程式碼的結構也較簡單。

UVa 10278 10740 10986

Single Source Shortest Paths:
Dial's Algorithm

用途

請參考Label Setting Algorithm的說明。

特別適用在每條邊的權重都是非負整數的圖上。

演算法

Label Setting Algorithm的變化版本。找不在樹上、離根最近的點,也可以直接把w[a]+d[a][b]的值通通拿去做Bucket Sort。

下面題供一個實作方式,每個bucket使用了Dijkstra's Algorithm的表格手法,以達到比較好的時間複雜度。一般的方式是以一個priority queue來實作一個bucket。

時間複雜度:進行Bucket Sort

一個bucket最多能有E個點,但是一個bucket最多只找V次最小值。所以總共是O(WV),其中W為bucket的數目,也是最長路徑長度值。

時間複雜度

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

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

值得一提的是,當圖上每條邊的權重皆為非負整數時,會有更好的時間複雜度。圖的資料結構為adjacency matrix的話,便是O(V^2 + W);圖的資料結構為adjacency lists的話,便是O(V+E + W)。

Single Source Shortest Paths:
Label Correcting Algorithm

用途

選定一個起點後,Label Correcting Algorithm可以求出此點到圖上各點的最短路徑,也就是最短路徑樹。並且可以順便判斷圖上是否有負環。

當圖上有負邊時,Label Setting Algorithm就無法使用,因為當下不在樹上、離根最近的點,其距離不見得是最短路徑長度。當圖上有負邊時,可以改用Label Correcting Algorithm,就算數值標記錯了,仍可修正。

演算法:求出最短路徑樹

回想一下,前面介紹relaxation說到:找到捷徑以縮短原本路徑。事實上,只要努力不懈地找捷徑,終會得到最短路徑。

一條捷徑如果很長,就不好辦了。一條捷徑如果很長,可以拆解成一條一條的邊,並一一嘗試以這些邊做為捷徑。只要不斷重複嘗試,一條一條的邊終會連接成一條完整的捷徑。

一開始想要不斷找捷徑,然而捷徑太多太長,只好多條捷徑拆解成一條條捷徑,一條捷徑拆成一條條邊,最後以邊為單位來進行relaxation,不斷重複利用目前算得的最短路徑長度值,這是Greedy Method的概念。

以relaxation的角度來看,Label Setting Algorithm與Label Correcting Algorithm的差異在於:Label Setting Algorithm知道該由哪個順序開始進行relaxation,所以可以逐步的設定好每個點的最短路徑長度值;Label Correcting Algorithm不知道正確順序,所以就只好不斷找捷徑,不斷校正每個點的最短路徑長度,直到正確為止。

演算法:偵測負環

如果一張圖上面有負環,那麼只要建立一條經過負環的捷徑,便會讓路徑縮短一些;只要不斷地建立經過負環的捷徑,反覆地繞行負環,那麼路徑就會可以無限的縮短下去,成為無限短。

一條最短路徑最多只有V-1條邊。當發現一個點被標記超過V-1次,表示其最短路徑超過V-1條邊(讀者請自行推敲),超過V-1條邊則必定經過負環!

附帶一提,Label Correcting Algorithm可以偵測圖中是否存在負環,但是無法找出負環所在,也無法找出所有負環。

演算法:找出最短路徑樹+偵測負環

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

1. 重複下面這件事,直到圖上每一條邊都無法作為捷徑:
 甲、找到一條可以做為捷徑的邊ab:d[a] + w[a][b] < d[b]。
 乙、以邊ab來修正起點到b點的最短路徑:d[b] = d[a] + w[a][b]。
 丙、如果b點被標記V次以上,表示圖上有負環。演算法立刻結束。

這裡提供一個常見的實作。用個容器把剛修正過的點暫存起來,以便後續修正。時間複雜度是O(VE)。

令w[a][b]是a點到b點的距離(即是邊的權重)。
令d[a]是起點到a點的最短路徑長度,起點設為零,其他點都設為無限大。
LIST是一個存放點的容器,可以是stack、queue、set、……。

1. 把起點放入LIST。
2. 重複下面這件事,直到LIST沒有東西為止:
 甲、從LIST中取出一點,作為a點。
 乙、找到一條可以做為捷徑的邊ab:d[a] + w[a][b] < d[b]。
 丙、以邊ab來修正起點到b點的最短路徑:d[b] = d[a] + w[a][b]。
 丁、將b點加到LIST當中。
 戊、如果b點被標記V次以上,表示圖上有負環。演算法立刻結束。

這個實作看起來就像是Dijkstra's Algorithm的精簡版。Dijkstra's Algorithm是一旦標記過的點就不再標記,至於Label Correcting Algorithm則是標記過的點可以再標記,差在這裡而已。

時間複雜度

每個點最多被標記V次,一個點一旦被重新標記後,就要讓該點所有出邊都嘗試進行relaxation。

每個點剛好都被標記一次時,就需時O(V+E);每個點剛好都被標記V次時,就需時O(V*(V+E)),可簡單寫成O(VE)。

所以建立最短路徑樹順便偵測負環,時間複雜度總共為O(VE)。

UVa 10557 10682

All Pairs Shortest Paths:
Label Correcting Algorithm

用途

Label Correcting Algorithm可以求出圖上任兩點之間的最短路徑,並順便偵測圖上是否有負環。

演算法

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

1. 重複下面這件事,直到圖上任兩點之間再也找不到捷徑:
 甲、找到i點到j點的捷徑i~k~j:d[i][k] + d[k][j] < d[i][j]。
 乙、更新i點到j點的最短路徑:d[i][j] = d[i][k] + d[k][j]。
 丙、如果d[i][j]被標記V次以上,表示圖上有負環。演算法立刻結束。

Single Source Shortest Paths:
Bellman-Ford Algorithm

用途

請參考Label Correcting Algorithm的說明。

特別適合用在能夠做平行處理的平台上,例如網路。

演算法:找出最短路徑樹

在Dijkstra's Algorithm之中,因為邊的權重都非負值,所以可由一個起點開始延伸拓展,來求得每一條最短路徑。但如果邊的權重為負值,Dijkstra's Algorithm就不管用了。

在Bellman-Ford Algorithm之中,便把圖上每一個點,同時都做為起點開始延伸拓展。如此一來就萬無一失。

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

1. 重複下面這件事V-1次。沒有負環的最短路徑最多只有V-1條邊。
 甲、延伸拓展圖上每一個點,延伸從這些點連出去的邊。
 乙、延伸之後把最短路徑長度存入d[]陣列。

由於每一個點的邊都會用於延伸拓展,也就是說圖上所有邊都會用於延伸拓展。因此,演算法可以寫得更簡潔:

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

1. 重複下面這件事V-1次。沒有負環的最短路徑最多只有V-1條邊。
 甲、把圖上每一條邊,用於延伸拓展。
 乙、延伸之後把最短路徑長度存入d[]陣列。

時間複雜度:找出最短路徑樹

圖的資料結構為adjacency matrix的話,便是O(V^3);圖的資料結構為adjacency lists的話,便是O(VE)。

以Label Correcting Algorithm的角度來看,Bellman-Ford Algorithm額外多做了一些沒必要的relaxation,所以效率上通常不如Label Correcting Algorithm。

演算法:偵測負環

如果一張圖上面有負環,那麼只要建立一條經過負環的捷徑,便會讓路徑縮短一些;只要不斷地建立經過負環的捷徑,反覆地繞行負環,那麼路徑就會可以無限的縮短下去,成為無限短。

由於Bellman-Ford Algorithm一共延伸了V-1次,理論上來說,已經把長度為V-1個邊以下、沒有負環的最短路徑都找出來了。如果真的是沒有負環的最短路徑,就不會再有捷徑。因此,如果還能再找到捷徑,那麼該條最短路徑就絕對包含負環。

時間複雜度:偵測負環

為一次Graph Traversal的時間。

UVa 558

All Pairs Shortest Paths:
Floyd-Warshall Algorithm

用途

請參考Label Correcting Algorithm的說明。

演算法:找出所有兩點之間最短路徑

請參考本站文件「Graph Theory─Transitive Closure: Warshall's Algorithm」。Floyd只是把Warshall's Algorithm套用在最短路徑問題上面罷了。

Applet:http://students.ceid.upatras.gr/~papagel/english/java_docs/allmin.htm

d(i, j, k) = min( d(i, k, k+1) + d(k, j, k+1), d(i, j, k+1) )
                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^  ^^^^^^^^^^^^
                  經過第k點                    沒有經過第k點

d(i, j ,k):紀錄由i點到j點的最短路徑長度,當中繼點遞迴到第k點的時候。

時間複雜度是O(V^3)。空間複雜度和Warshall's Algorithm類似,使用Dynamic Programming紀錄每個小問題的答案。另外,由於計算順序以及最小值運算的關係,造成記憶體可以重複使用,只需要開二維陣列。

有兩種紀錄路徑的方法。

演算法:偵測負環

除了使用Bellman-Ford Algorithm的方式以外,另外還有個更直觀的檢查方法:

d[i][j]意指著一條由i點走到j點的最短路徑長度。以d[i][i]來說,其實它代表著一條由i點出發,周遊在外,最後繞一圈回到i點的最短路徑長度──它亦是一只環。因此,如果d[i][i]這條繞一圈的路徑長度是負值,就表示這是一只負環,或者表示這條路徑包含負環、這條路徑以負環作為捷徑。

最後,只要檢查所有可以做為環的起點的i點,就可以知道圖上有沒有負環。

偵測連通

要偵測由一個點到另一個點連不連通,可以在起點使用遍歷演算法,或者之前所述的最短路徑演算法,若可由起點到達終點,便是連通。然而一次只能計算一個起點到其他點連不連通。

使用Floyd-Warshall Algorithm,就可以一口氣算出圖上各點之間連不連通。相當方便。

圖的資料結構為adjacency matrix的話,那麼不管是用DFS、BFS還是Floyd-Warshall Algorithm來計算所有點之間的距離(或者連通),時間複雜度都是一樣多的。圖的資料結構為adjacency lists的話,則DFS、BFS可能會因為邊的數量少,而會快一點;然而事實上Floyd-Warshall Algorithm的程式碼比較乾淨俐落,實際效率通常不比DFS、BFS差的!各位可以自行斟酌一番。

運用Floyd-Warshall Algorithm

一個問題若有下述性質,則可嘗試Floyd-Warshall Algorithm:

一、繞路:由i點到j點時,若繞路結果會更好的話,那就一定要繞路。但是至多只能將所有點都恰好繞過一次,絕不能重複地經過同一點,否則會照下面第二點所述,使結果變成無窮無盡的好,產生無限循環。

二、最佳化:只要由i點到j點有辦法變得更好的時候,其他事物也一定可以同時共用、享受這個由i點到j點的好處。附帶一提的是,有一種特殊情況是「無限循環」:i到j讓a到b變好,a到b讓i到j變好,不斷循環下去,變成無窮無盡的好。負環也是無限循環的一種。

三角不等式 v.s. 繞路性質

三角不等式是指兩邊長的和必大於第三邊、兩邊長的差必小於第三邊。方才提到的繞路性質則是指兩邊長的和最好小於第三邊(三角形的邊成了路徑、兩邊和成了距離),和三角不等式有點類似,但不完全相同。

UVa 104 125 280 423 436 534 544 567 10048 10099 10246 10342 10987

All Pairs Shortest Paths:
Johnson's Algorithm

用途

求出圖上所有兩點之間的最短路徑,順便偵測凸上是否有負環。

Johnson's Algorithm可以說是加強版的Dijkstra's Algorithm。由於Dijkstra's Algorithm無法用於邊的權重為負數的情況,所以Johnson's Algorithm首先重新調整邊的權重為非負數,並順便檢查圖上是否有負環,接著才放心的使用Dijkstra's Algorithm來計算所有兩點之間的最短路徑。

重新調整權重

要如何調整權重,才不會影響最短路徑的路線呢?

這裡介紹一個巧妙的方法:首先把圖上每一個X點都設定一個權重h(X),然後將一條由A點到B點的邊的權重w(A, B),重新調整成w'(A, B) = w(A, B) + h(A) - h(B)。

此時,任取圖上的一條路徑S~T,其路徑長度就變成了:

  w'(S~T)
= w'(S-a-b-…-x-T)
= w'(S,a) + w'(a,b) + … + w'(x,T)
= [ w(S,a)+h(S)–h(a) ] + [ w(a,b)+h(a)–h(b) ] + … + [ w(x,T)+h(x)-h(T) ]
= w(S,a) + w(a,b) + … + w(x,T) + h(S) - h(T)
= w(S-a-b-…-x-T) + h(S) – h(T)
= w(S~T) + h(S) – h(T)

一加一減相消後,可以推導出簡潔的結果。

由S點到T點的各條路徑的長度之中,其h(S)和h(T)都是定值,於是乎w(S~T)增減之時,w'(S~T)亦會同進退,長度的大小關係依舊不變,於是乎由S點到T點的最短路徑也就不動了。

我們再看看圖上的環:

  w'(S~S)
= w'(S-a-b-…-x-S)
= w(S-a-b-…-x-S) + h(S) – h(S)
= w(S~S)

圖上的環不會因調整權重而改變。就算是圖上有負環,最短路徑的存在性不會因調整權重而改變,

重新調整權重為非負數

調整權重而不會影響最短路徑的方法已經有了。現在要想想如何好好設定h(X)的值,讓每一條邊的權重都可以調整為非負數。

Johnson發現:最短路徑找到後,圖上每一條邊都不可能再做relaxation,而當起點只有一個時,式子可寫成d(A) + w(A, B) >= d(B),經過移項之後就是w(A, B) + d(A) - d(B) >= 0,正好就是調整權重的式子。因此,只要令h(X)是由一個起點到各個X點的最短路徑長度,那麼調整後的權重就是非負數;無論起點是哪一點,這個式子都會成立。

至於起點該選在哪裡好呢?注意到圖上的每一條邊都要重新調整權重、圖上每個點都必須設定h(X)值,因此選定的起點建立最短路徑樹後,必須涵蓋圖上每一個點,如此圖上每一個點才會有h(X)值。

找起點頗麻煩。Johnson想出了一個絕妙方法,不必找起點:

1. 在圖上增加一個點,並建立此點連向圖上其他點的邊,權重設定為零。
   如此找出的最短路徑樹必可涵蓋圖上所有點。
2. 由此點作為起點,執行Bellman-Ford Algorithm。
 甲、由此點到各個X點的最短路徑長度,作為h(X)。
 乙、順便檢查圖上是否有負環。
3. 移除新增的點及邊,還原這張圖。
4. 調整圖上每一條邊的權重:由A點連到B點的邊,令其權重為w(A, B)。
   新的權重為w'(A, B) = w(A, B) + h(A) - h(B)。

Johnson's Algorithm

1. 調整圖上的邊為非負數。
2. 圖上每一點都做為起點,分別執行Dijkstra's Algorithm,
   以找出圖上任兩點之間的最短路徑。
3. 找出最短路徑後,對照原來的邊的權重,重新求出正確的最短路徑長度。
   或者直接利用h(X)逆推:w(S~T) = w'(S~T) – h(S) + h(T)。

時間複雜度

當圖上的邊很少時,做一次Bellman-Ford Algorithm以及做V次Dijkstra's Algorithm,比做一次Floyd-Warshall Algorithm還快一點點。各位可以算一算時間複雜度。

以最短路徑長度重新調整權重

附帶一提,以最短路徑長度重新調整權重的話,所有最短路徑上的邊,其權重都會變成零。當要找出一張圖所有的最短路徑時,這是一個很好用的特性。

Single Source Shortest Paths: Scaling(Gabow's Algorithm)

用途

選定一個起點後,Gabow's Algorithm可以求出此點到圖上各點的最短路徑,也就是最短路徑樹。但是有個限制是:圖上每一條邊的權重都是非負整數。

演算法

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

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

Scaling的精髓,在於每次增加精細度後,必須有效率的修正前次與今次的誤差。此演算法巧妙運用調整權重的技術,確切找出前次與今次差異之處,而得以用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)

【待補程式碼】

找出最短路徑樹(adjacency lists)

【待補程式碼】

Single Source Shortest Paths in DAG:
Topological Sort + Dynamic Programming

Topological Sort + Dynamic Programming

在有向圖上選定一個起點後,求出起點到圖上各點的最短路徑,也就是最短路徑樹;也可以選定一個終點後,求出圖上各點到終點的最短路徑。但是有個限制是:此有向圖上不得有環(Directed Acyclic Graph, DAG)。

讀者可先參考「Graph Theory─Topological Sort」。

演算法

一張圖經過Topological Sort之後,便可以確定圖上每一個點只會往排在後方的點走去(由排在前方的點走過來)。計算順序相當明確,因此可以利用Dynamic Programming來計算各條最短路徑。

找出最短路徑樹(adjacency matrix)

迴圈的部分還有另一種寫法。

時間複雜度

時間複雜度約是兩次Graph Traversal的時間複雜度。圖的資料結構為adjacency matrix的話,便是O(V^2);圖的資料結構為adjacency lists的話,便是O(V+E)。

UVa 10000