如果我們只在乎從某個點 s 出發到所有點的距離，而這張圖的所有邊權重都是非負的，那麼我們可以使用 Dijkstra 的演算法來解決這個問題。Dijkstra 演算法的核心概念是這樣的：我們可以從 s 開始繪製同心圓，並且不斷地擴大它直到碰到下一個距離最近的點為止；接著，我們更新這個點相鄰的點到 s 的距離，並且繼續擴大這個同心圓。當所有點都被碰到的時候，這個演算法便能正確地找出 s 到所有點的最短距離了。
如果我們使用 Fibonacci Heaps 或是 Brodal Queue，那麼理論複雜度可以變成 O(m+n log n)，當圖上的邊很多的時候，就會變成線性時間。一些相關的實驗可以參考：
https://github.com/gabormakrai/dijkstra-performance
如果一個矩陣的每一格的數值都是一個介於 [-M, M] 之間的整數、或是一個代表無窮大的數值；那麼我們可以用普通的矩陣乘法來模擬 (min, +)-矩陣相乘，並且在 Õ(Mn^ω) 的時間內完成(Õ 表示我們省略 log 項)。要怎麼做呢？
假設有兩個矩陣 A 和 B，其每一格都是一個介於 [-M, M] 之間的整數，那麼我們可以建立另外兩個矩陣 A’ 和 B’，其中 A’[i, j] = (n+1)^(A[i, j] + M)、B’[i, j] = (n+1)^(B[i, j] + M)。(也就是說，我們將負數墊高) 此外，我們將無窮大視為 3M 就可以了。
接著，我們可以用平常的矩陣相乘把 A’ 和 B’ 乘起來，我們假設平常用的電腦，進行加減乘除每一次只能處理 O(log n) 位元，因此對於 C’ = A’ * B’ 矩陣內的每一格，其數值可能高達 n(n+1)^6M 這麼大，要表達這樣的數字必須要使用 O(M + log n) 大小的記憶體；對於這樣的數字進行加減乘除，大概也需要 Õ(M) 的時間。把 A’ 和 B’ 乘起來的步驟，需要花 Õ(Mn^ω) 的時間。找出 C’ 以後，要怎麼得到真正的 min{ A[i, k] + B[k, j] } 的數值呢？我們注意到，如果最小的 A[i, k]+B[k, j] 是 y，那麼 (n+1)^(y+2M) 必定會整除 C’[i, j]。而且，(n+1)^(y+2M+1) 不會整除 C’[i, j]。因此我們可以用二分搜尋法，在 O(log M) 的時間內找出正確的 y 值。
於是，還原出矩陣 C = A ⋆ B 只要 Õ(Mn^ω) 的時間就好！
有了上述的乘法利器，我們仍然沒辦法計算最短路徑長度。為什麼呢？因為就算每一條邊的長度都不超過 L，最短距離出現在矩陣上仍然可能高達 L * n，也就是說套用上述矩陣相乘需要代入 M = L * n，時間複雜度就必定超過 n^3 的 Floyd-Warshall 演算法，相當不划算！
對此，我們可以採取折衷的策略：首先，我們先隨機挑選 (n/k) log n 個點，其中 k 是一個待定的參數。挑選完畢後，對這些選出來的點 {x1, x2, …}，以它們為起點和終點分別做一次 Dijkstra 演算法，求得從 dist(x, ?) 和 dist(?, x) 的最短路徑長度。
還記得我們之前提到的 “跳躍次數” (hops) 嗎？不難發現，如果從 s 到 t 的最短路徑需要的跳躍數超過 k 的話，有很高的機率，剛才選到的 {x1, x2, …} 其中一個點 x 會出現在 s 到 t 的這條最短路徑中間。換句話說，此時的我們只要花費 O(n/k) 時間計算 min_x { dist(s, x) + dist(x, t) } 就能得知 s 到 t 的最短路徑了。因為總共有 n^2 個點對，所以我們可以利用 O(mn/k + n^3/k) 的時間在很高的機率下找出所有跳躍次數超過 k 的最短路徑。
至於沒那麼跳的最短路徑，跳躍次數不超過 k 的，它的路徑長也不會超過 kM。因此我們可以用倍增的方法，套用剛才的 (min, +)-矩陣相乘，在 Mn^ω + 2Mn^ω + 4Mn^ω + … + kMn^ω = Õ(kMn^ω) 的時間內就可以搞定它。
因此，如果我們把長跳跟短跳的方法都用上，時間複雜度會是 Õ(kMn^ω + n^3/k)。折衷選定 k 的值，就可以得到一個 Õ(M^0.5 n^((3+ω)/2)) 時間複雜度的最短路徑演算法啦！
http://people.csail.mit.edu/virgi/6.890/lecture4.pdf
https://logic.pdmi.ras.ru/ssct09/slides/SSCT09_Uri_Zwick.pdf
iThome鐵人賽
看影片追技術