浙江大學-數據結構-小白專場：最小路徑問題-7.1.4

02-25

多源最短路演算法

之前我們說過可不可以把單源最短路的演算法對每一個頂點實施一次呢？當然是可以的，我們第一個簡單粗暴的方法就是直接把單源最短路演算法調用這麼多遍，

調用這麼多遍在某種情況是比較適用的，比如說如果這個圖是比較稀疏的話，我們前面說了，它的時間複雜度可以達到O(VlogV),調用V遍以後，就是再乘以一個V上去，就是O(V^2logV)，它還是比較好的，但是對於稠密圖來說呢，它就要在原來的V^2+E再乘以V,

所以這個演算法對於稀疏圖是比較好的

對於稠密圖來說，我們就要有方法二，Floyd演算法

看上去這兩個演算法都是O(V^3)，但是呢，方法2是真正的O(V^3)，沒有上面方法一的尾巴，對於稠密圖來說，它的效果更好一點

Floyd演算法怎麼運行的呢？其實跟Dijkstra有點相似，也是說每一條最短路，不是一次成型的，是逐步成型的，既然我們是在講一個稠密圖，我們通常就用鄰接矩陣來記這個稠密圖，Floyd演算法定義了一個二維數組，也就是一個矩陣

這個矩陣的第i,j個元素定義的是這個路徑的最小長度，從i到j,但是只經過一部分頂點，看到這個k了沒有，只經過編號小於等於k的那些頂點，它的最短路徑的長度，那麼最終我們要的路徑是什麼樣的呢？假如說我們的頂點編號是從0開始，一直變到V-1的，當這個k變到V-1的時候，那麼這個路徑就是真正的最短路徑了，所以我們的最短路徑是一步一步生成的，是從 $D^0$ 開始，就一開始我們只考慮一個頂點，0號頂點，進去的時候，然後一步一步的遞推，到最後我們得到了 $D^{|V|-1}$ 這個矩陣就存的是i到j的真正最短距離，那麼這裡頭我們的問題又來了，最初的D,因為我們從0開始記嘛，在往前推我們把它取個名字叫做 $D^{-1}$ ,也就是初始的矩陣，應該怎麼定義呢？其實D的初始化很簡單，就直接把它定義為鄰接矩陣就對了，主對角線上全部是0，如果i和j之間有一條邊的話，D[i][j]就定義這條邊的權重，還有下一個問題，如果i和j之間沒有直接的邊相連的時候，這個元素應該定義成什麼呢？

這個值的初始化也不能隨便給，在最短路演算法裡面，如果兩個頂點之間沒有直接邊的話，那它必須要初始化正無窮，後面才能慢慢的把它變小，最關鍵的步驟就是我們要怎麼從一個D推到下一個D去，遞推的原理是什麼樣的呢？那我們看對中間任何一步k,如果前面 $D^{k-1}$ 步已經完成，我們遞推到 $D^{k}$ 的時候，我們會面臨兩種可能：第一種可能是新收進來的頂點k,它根本就不影響i到j的最短路徑，它不到最短路徑里，所以我們是沒有必要去更新這個路徑的，我們只要保持原樣就好，如果新加進去一個k,影響i到j之間的最短路的話，那麼很顯然的，k一定是在最短路徑上，就是從i到j的最短路必須會經過k,更重要的是，這個路徑一定是由兩段最短路徑組成的，也就是說，把k加進來以後，i到j之間的距離，一定是等於從i到k的最短距離加上從k到j的最短距離，那麼i和k之間的距離，以及k和j之間的距離，中間都不包含頂點k的，所以這兩個距離應該是在第k-1步的時候，就已經求出來了，所以我們要做的是什麼呢，就是在遞推到下一步的時候，我們算一下這個距離，如果更短的話，那我們就更新一下，把它更新成更短的距離

這就是非常簡單的Floyd演算法程序

一開始的時候我們把D[i][j]初始化就是它的鄰接矩陣(D[i][j] = G[i][j]),然後對於每一個k,k就是我們的上標，從0開始，一步一步的向後推，對於每一個k來說，我去檢查對於每一對i，j,我去檢查第i，j的值，如果D[i][k] + D[k][j]是一個更小的值的話，那麼我把這個值來更新一下，這個基本上就是Floyd演算法的全部了，我們看還空了一點空，這個空是留給什麼的呢？如果我們不僅要計算i,j之間的最短句，還要求輸出它們的兩個之間的最短路徑，要怎麼辦呢？我們需要另外一個二維數組來記錄它們的路徑，那麼這個二維數組初始化成-1，是一個負數就表示i，j之間現在是沒有路徑的，當這個路徑在這一步被更新的時候(D[i][j] = D[i][k] + D[k][j]),就意味著在i到j之間，一定會經過k,那麼我們就把k記在path[i][j] = k這個元素里，這樣記錄了以後，我們就可以很容易的把i到j之間的最短路徑也列印出來，怎麼列印呢？這其實是一個非常簡單的遞歸，我如果要列印從i到j的最短路徑，那麼這個最短路徑一定是由從i到k的最短路徑，加上k，加上k到j的最短路徑這麼三段組成的，所以我這個程序就可以遞歸列印從i到k的路徑，然後把path[i][j]的值，這個k打出來，然後再遞歸的去列印從k到j的那段路徑就可以了，那我們注意到這裡有三重for循環的嵌套，所以可以非常簡單的得到Floyd演算法的時間複雜度就是O(|V|^3)