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