1. Floyd-Warshall 演算法

2021-06-11 00:12:48 +0800 CST Tags: dp, floyd-warshall

問題：給定一張沒有負環的帶權有向圖 (weighted directed graph) $G$，請求出該圖任意兩點間的最短距離。

解法：每一張沒有負環的圖都有一個良好的性質，那就是任意兩相異 (單向) 連通的頂點間至少有一條最短路徑並不包含任何環，因為圖上每個環的權重和皆大於或等於零，加上它們只會讓路徑變遠或持平，因此對於每一條最短路徑，它們上面的環通通都可以拔掉而且不影響連通性，拔掉之後的結果就會造成每條最短路徑上的每個頂點都至多只會出現一次，而這對我們接下來要引進的數學歸納法來說是個非常重要的理論基礎。

一開始任兩點 $(u,v)$ 間的暫時最短距離可以初始化為 (a) $0$，如果 $u=v$；(b) $w(u,v)$，如果 $u\ne v$ 同時 $u$ 和 $v$ 之間存在至少一條邊且這之中最小的權重為 $w(u,v)$；(c) $\infty$，如果 $u\ne v$ 而且 $u$ 和 $v$ 之間沒有任何邊存在。那現在假設每次第 $k$ 回合開始之前我們就已經算出任意兩點間所有符合除了起訖點以外的中繼點 (若存在) 號碼都不超過 k-1 的路徑之中最短的距離，那麼要如何根據這些資訊在這回合結束後就能算出任意兩點間所有符合除了起訖點以外的中繼點 (若存在) 號碼都不超過 k 的路徑之中最短的距離呢？方法很簡單，符合後者條件的可能路徑其實又可以再分成兩類，(a) 中繼點不通過頂點 $k$ 的跟 (b) 中繼點有通過頂點 $k$ 的，(a) 類在前一個回合就已經算出，而 (b) 類根據我們第一段標註底線的結論，必定形如 $u \dots k \dots v$ 而且前半段 $u \dots k$ 與後半段 $k \dots v$ 的中繼點皆不包含 $k$，於是它們的最短距離亦皆已經在前一個回合先行算出，這麼一來要設計遞迴式就簡單多了！

令 $u$ 到 $v$ 之間所有符合除了起訖點以外的中繼點 (若存在) 號碼都不超過 k-1 的路徑中最短距離是為 $d_{k-1}(u,v)$，那下一回合的 $d_k(u,v)$$=\min\{\ d_{k-1}(u,v),\ d_{k-1}(u,k)+d_{k-1}(k,v)\ \}$，持續對任意兩點 $(u,v)$ 計算這個遞迴式 $|V|$ 個回合之後的 $d(u,v) = d_{|V|}(u,v)$ 即為從 $u$ 走到 $v$ 的最短距離。細心的讀者可能會發現下方的程式碼實作是 in-place 修改，整個陣列並沒有區分為前後兩個回合，其實這樣不會影響到正確性，因為很明顯地 $d_k(u,k) = d_{k-1}(u,k)$ 而且 $d_k(k,v) = d_{k-1}(k,v)$。另外，以距離無限大作為不連通的代名詞也只是為了實作上的方便，只要我們確保第 11 行的遞迴式在計算結果為不連通的時候同樣會得到一個代表無限大的值，那程式就仍然是正確的；如果很不幸地某些變形的遞迴式剛好就是沒辦法那麼順利，我們還是可以把不連通的路徑都分開來討論，還是能體會到這套演算法的威力。

總結：這個演算法的適用時機並不僅限於求解兩點間的最短距離這個模型，只要滿足：

初始條件：任何沒有中繼點的最佳路徑之答案都要能先初始化，包含 $d(v,v)=0$ 以及如果邊 $(u,v)$ 存在的話 $d(u,v)=w(u,v)$。
遞推條件：必定存在一種最佳路徑不包含環，同時該路徑內的子路徑亦為最佳路徑。
連通代值：(optional) 如果可以找到一個值代表不連通，而且 2. 的遞推式不會破壞掉這個設定。

這三個條件的模型都適用，特別地如果 3. 不滿足，我們也可以把遞推式修改成另外考慮不連通的版本，這套演算法仍然成立。

例如：

邊權重代表非負噪音程度，目標是希望行走過程中所路過之最吵雜的邊要愈不吵雜愈好，那麼：
1. 初始條件：不出門勢必能阻隔所有噪音而且吵雜度為 0，另外任兩點之間的邊總是可以挑最不吵雜的來走。
2. 遞推條件：最佳路徑可以沒有環，因為如果最吵雜的邊是在環上，那拔掉該環之後剩下的其他地方本就不會如該環那麼地吵雜，而且仍然到得了目的地；如果最吵雜的邊不在環上，那麼拔掉該環後並不會降低剩下其他地方裡面最吵雜的邊造成的噪音，而且目的地仍然可抵達；如果一個最佳路徑內有子路徑非該段的最佳路徑，那麼將其調整為該段的最佳路徑之後也不會惡化原本整段最佳路徑的答案。
3. 我們的遞迴式為 $d_k(u,v)=\min\{\ d_{k-1}(u,v),\ \max\{d_{k-1}(u,k), d_{k-1}(k,v)\}\ \}$，它也能保持無限大等價於不連通這件事。
以上三點都成立，這個模型便可以使用 Floyd-Warshall 演算法。練習題有 zerojudge 的 a674、c125。

提醒：大部分模型的邊權重都是非負值，但是這個演算法的要求僅為無負環，出現適度的負邊是允許的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


int V=, E=; // V:=點數、E:=邊數
int d[V][V]; // 距離陣列

memset(d, 0x3f, sizeof d); // 初始化 1: 不超過 INT_MAX / 2 的最大值 (以免第 11 行的加法溢位)
for (int i=0; i<V; i++) d[i][i] = 0; // 初始化 2 (全域陣列會自動完成)
for (int a, b; E--;) cin >> a >> b >> d[a][b]; // 初始化 3

for (int k=0; k<V; k++)
    for (int i=0; i<V; i++)
        for (int j=0; j<V; j++)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

int a, b; cin >> a >> b; // 詢問從 a 走到 b 的最短距離
cout << ((d[a][b] == 0x3f3f3f3f) ? "no path" : to_string(d[a][b])) << '\n';