iT邦幫忙

2021 iThome 鐵人賽

DAY 13
0
Software Development

圖論與演算法之間的相互應用系列 第 13

最短路徑問題 (1)

9.4 關於三連通的練習題

這題超難,我把連結放這邊就好。
https://acm.timus.ru/problem.aspx?space=1&num=1819

10 最短路徑

最短路徑的用途相當廣泛,大家應該可以隨手想出很多應用。
常見的最短路徑問題根據需求,可以分成很多種類,比方說單一源點最短路徑 (Single Source Shortest Paths, SSSP)、或是所有點對最短路徑 (All Pair Shortest Paths, APSP)。今天我們簡單描述一個動態規劃的概念,可以解決以上兩個問題。

10.1 單一源點最短路徑 SSSP

給你一個有向圖 G,每一條邊上有一個權重代表它的距離。在單一源點最短路徑問題中,我們給定一個起點 s,目標是計算出從起點 s 到任何圖上到的了的地方的最短距離。
首先,不難證明出任何兩個點之間的最短路徑,可以只由不超過 n-1 條邊就可以抵達。這個最短路徑所使用的邊數,我們通常稱之為跳躍 (hop)。

我們可以利用動態規劃來描述此事:定義 dp[k, v] 表示使用不超過 k 次跳躍就能從 s 抵達 v 的最短距離。那麼此時會有 dp[k, v] = min{ dp[k-1, u] + weight(u, v) }。也就是說,我們可以透過枚舉抵達 v 的前一步是哪個點,來找出到 v 的最短距離。我們可以發現,計算 dp[k, 1..n] 的時候可以直接利用 dp[k-1, 1..n] 的空間。此外,如果我們最終目的是只要找最短距離,不在乎跳躍數的話,我們甚至可以直接更新在當前的 dp[*, v] 表格上,因此這個表格的第一維可以直接拿掉,只要保證我們有對所有邊依序更新總共 n-1 輪就可以了。而這個方法便是為 Bellman-Ford 演算法。

這個演算法的時間複雜度是 O(nm),其中 n 是點數、m 是邊數。

10.2 所有點對最短路徑 APSP

這個題目的目標,是要回傳一個矩陣 A,使得 A[s, t] 表示從 s 到 t 的最短路徑長度。類似地,我們可以發現引入跳躍數的概念,定義動態規劃表格 dp[k, s, t] 表示從 s 到 t 使用不超過 k 次跳躍的最短路徑,一樣也可以用前面 Bellman-Ford 的概念找出答案:dp[k, s, t] = min{ dp[k-1, s, u] + weight(u, t) }。但這樣計算出來需要的時間是 O(n^2m) 的,在圖中有很多條邊的時候,比較沒有效率。

有沒有辦法加速呢?有兩種加速的方法,一種是預處理這張圖,讓他的邊數變得很稀疏,但是卻又保有原本圖 G 上面最短路徑的結構,這樣產生出來的圖 H 我們稱為圖 G 的路長保留圖 (distance preservers)。這個保留最短路徑結構的方法,在圖非常巨大的時候很好用,因為此時我們甚至可以把原圖丟掉,降低儲存空間但又能達到計算最短路徑的目標。我們在未來幾天會再次與大家詳細介紹。

另一種加速的方法,是每次計算都讓跳躍次數加倍:dp[k, s, t] = min{ dp[k/2, s, u] + dp[k/2, u, t] }。由於 k 不超過 n-1,如此一來用每次加倍的方法,我們就只要更新 log(n-1) 次的表格就行了。時間複雜度是 O(n^3 log n)。

Floyd-Warshall 演算法採用了截然不同的動態規劃策略:定義 dp[k, s, t] 表示被允許使用編號 1…k 作為中繼站時,從 s 到 t 的最短路徑長度。此時就會有 dp[k, s, t] = min{ dp[k-1, s, t], dp[k-1, s, k] + dp[k-1, k, t] },注意到計算一個 dp[k, s, t] 狀態需要的時間從 O(n),變成了常數了!因此時間複雜度漂亮地降至 O(n^3)。


上一篇
圖的連通 (6)
下一篇
最短路徑問題 (2)
系列文
圖論與演算法之間的相互應用30

尚未有邦友留言

立即登入留言