全點對最短路徑

什麼是全點對最短路徑呢？顧名思義，就是要對於全部的有序點對 $u, v$、計算出 $u$ 走到 $v$ 的最短路徑。

我們一樣考慮在帶權有向圖上的情況，那聽起來還不簡單——既然我們在最短路徑都知道 Dijkstra 可以在 $O(N^2)$ 或 $O(M\log M)$ 的時間找到給定任意起點到其他所有點的距離了，那我們就對於每一個起點都跑一次 Dijkstra、這樣就有 $O(N^3)$ 或 $O(NM\log M)$ 時間複雜度的演算法啦！

講得沒錯，但如果只會 Dijkstra 就太落伍了，實際上如果只是要算全點對最短路徑，有一個簡短到不能再簡短的演算法可以使用，若在比賽中處理全點對最短路徑還要慢慢刻 Dijkstra 的話，就先輸一半了。

本文要介紹的唯一一個演算法，就是計算全點對最短路徑時任何人都應該要懂得嘗試使用的演算法，Floyd-Warshall 演算法。

講得這麼厲害，我們先直接來看看他寫出來長成什麼樣子：

vector<vector<int>> dis(n, vector<int>(n, INF)); // 初始化任兩點之間的最短路徑成無限大
for (auto [u, v, w] : edges) // 初始化有直接連邊的距離成對應邊權
    dis[u][v] = w;
for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

沒錯，就只有這樣！是否被他的簡短所震驚了呢？這樣短的演算法看似玄幻，其背後的原理以我們現有的知識是解釋得通的，就讓我們來一一剖析他。

Floyd-Warshall 演算法的第一步，就是先幫全點對最短路徑找到一種特殊的「子結構」。

什麼意思呢？就好比我們在解一般的最短路徑時，利用到了「鬆弛」的想法，在發現有一條邊 $u, v$ 使得起點 $s$ 先走 $u$、再走 $v$ 時，會比原本我們已知的 $s$ 到 $v$ 的最短路徑還短時，我們就去把 $s$ 到 $v$ 的最短路徑更新成「先從 $s$ 走我們已知的最短路徑到 $u$、再走到 $v$」這條路。換個角度想，這裡我們就能說，$s$ 到 $v$ 的最短路徑，有一個「$s$ 到 $u$ 的最短路徑」的子結構。

Floyd-Warshall 把這個概念稍作延伸，誰說用來鬆弛的只能是邊呢？如果我們要找到 $s$ 到 $v$ 的最短路徑，要是我們能夠提前算好 $s$ 到 $u$ 的最短路徑、以及 $u$ 到 $v$ 的最短路徑，那直接計算 $d(s, u) + d(u, v)$ 就可以得到一條 $s$ 到 $v$ 的路徑了！

為什麼要這樣延伸呢？想法上是因為既然我們都要計算「全點對」的最短路徑，那自然就會希望所有點對之間能夠更相輔相成的互相幫大家把最短路徑算出來。相較於「單源點」的最短路只有從 $s$ 出發的路徑可以用，有「全點對」的資訊讓我們擁有更多武器可以做使用，想像上也許就會有一個比較有效率的做法。

相信前面把話題往子結構帶時讀者已經猜到，有了子結構，就可能出現重複子問題——Floyd-Warshall 演算法的優化關鍵就是使用動態規劃。

但說得漂亮，我們才在動態規劃的必要元素提到，動態規劃的狀態必須有「無後效性」。如果我們令 $\mathrm{dp}[i][j]$ 是 $i$ 到 $j$ 的最短路徑，硬是用這個狀態寫出轉移式的話，就會得到：

$$
\mathrm{dp}[i][j] = \min_{k\in V}\{\mathrm{dp}[i][k] + \mathrm{dp}[k][j]\}
$$

不過這不對吧？這樣各狀態之間不就互相轉移了嗎？

為了避免這種狀況，我們需要做一些「發明」，就像我們在講解無後效性時提到的，幫最短路徑找到一個「計算的順序」。

Floyd-Warshall 的做法是，觀察到一條 $s$ 到 $t$ 的路徑有兩種分類：

• 直接由一條邊 $(s, t)$ 所形成。
• 路徑上有一些不是 $s, t$ 的點，稱做「內節點」。

由於所有最短路徑都預計是簡單路徑，這個內節點就成了我們「創造路徑」的關鍵。想像上，我們就可以從大家都是單條邊出發，不斷的把路徑用內節點拼接起來。

不過要用什麼順序拼接呢？這裡最直接的方法就是利用「最大的內節點編號」來做為最後一次拼接。由於最短路徑會是簡單路徑，假設一條路徑 $s$ 到 $t$ 中的最大內節點為 $x$，那麼這條路徑就可以被拆解成 $s$ 到 $x$ 加上 $x$ 到 $t$，並且這兩段子路徑的「最大內節點編號」一定都比 $x$ 來得小，這樣我們就成功獲得一組順序了！

因此，在 Floyd-Warshall 中，所謂的動態規劃狀態即為：

• $\mathrm{dp}[k][i][j]$ 為從 $i$ 出發、$j$ 結尾、且最大內節點編號不超過 $k$ 的最短路徑。

此時我們就能寫出轉移式：

$$
\mathrm{dp}[k][i][j] = \begin{cases}
\infty & k=-1 \text{ 且 }i\text{ 和 }j\text{ 之間沒有邊} \\
w(i, j) & k = -1 \text{ 且 }i\text{ 和 }j\text{ 之間有邊} \\
\min(\mathrm{dp}[k - 1][i][j], \mathrm{dp}[k - 1][i][k] + \mathrm{dp}[k - 1][k][j]) & k \geq 0 \\
\end{cases}
$$

如此一來，這個動態規劃的狀態數就是 $O(N^3)$，轉移是 $O(1)$，總共的時間複雜度就是 $O(N^3)$。

注意到這裡我們用 $k=-1$ 來表示還沒有任何內節點的初始狀態值，這只是一種偏數學的表示法，實際實作上其實不會真的這樣寫，讀者可以先理解一遍上方這個動態規劃的意義後，再往下看看為什麼最後我們可以把 Floyd-Warshall 寫得像一開始給的程式碼一樣輕巧又簡短。

開一個三維陣列其實挺累的，這裡我們就搬出我們在基礎動態規劃 / 滾動 DP所學到的技巧，觀察到這個動態規劃的轉移中，$dp[k]$ 對應到的整張表格，其實只有用到 $dp[k-1]$ 而已，這表示我們肯定可以只開兩個二維表格就能進行滾動 DP。

但其實還可以再更好，不像背包問題，在最短路徑中，我們並不在乎「同一段路徑被取用兩次」這種在背包問題會出事的狀況，所以自然的我們也不需要像背包問題一樣，還要故意反過來跑來特別迴避重複取用物品。那就簡單了，我們可以直接「原陣列原地利用」來對答案更新，也因此我們就能得到最一開始那份看起來短得誇張的程式碼了。

Floyd-Warshall 不僅簡短，由於他本身也幾乎只有很單純的迴圈和取最小值的操作，所以在常數上表現也非常優秀。事實上在一些速度不慢的 OJ 上，當點數大到 $1000$ 個點時，Floyd-Warshall 都還有可能跑得動，是非常厲害的一個演算法。

這樣一個乾淨的演算法，其背後用到的理論卻不簡單，針對這樣的動態規劃運用方式，讀者是否有從他身上學到什麼呢？

上面這題存在時間複雜度更優的做法，但做法本身稍微複雜許多，讀者可以嘗試只用本文章學到的知識來解題。