一、floyd算法為什么要用鄰接矩陣實現(xiàn)而不用鄰接表

floyd算法要用鄰接矩陣實現(xiàn)而不用鄰接表是因為需要O(1)時間查詢?nèi)我鈨蓚€頂點的邊權(quán)值，在這一句中：d(i, j) = d(i, k) + d(k, j)。Floyd 算法是一個基于「貪心」、「動態(tài)規(guī)劃」求一個圖中 所有點到所有點 最短路徑的算法，時間復雜度 O(n3)。

1)算法思想原理：

Floyd算法是一個經(jīng)典的動態(tài)規(guī)劃算法。用通俗的語言來描述的話，首先我們的目標是尋找從點i到點j的最短路徑。從動態(tài)規(guī)劃的角度看問題，我們需要為這個目標重新做一個詮釋（這個詮釋正是動態(tài)規(guī)劃最富創(chuàng)造力的精華所在）

從任意節(jié)點i到任意節(jié)點j的最短路徑不外乎2種可能，1是直接從i到j(luò)，2是從i經(jīng)過若干個節(jié)點k到j(luò)。所以，我們假設(shè)Dis(i,j)為節(jié)點u到節(jié)點v的最短路徑的距離，對于每一個節(jié)點k，我們檢查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，證明從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，我們便設(shè)置Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來，當我們遍歷完所有節(jié)點k，Dis(i,j)中記錄的便是i到j(luò)的最短路徑的距離。

2)算法描述：

a.從任意一條單邊路徑開始。所有兩點之間的距離是邊的權(quán)，如果兩點之間沒有邊相連，則權(quán)為無窮大。 　　

b.對于每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。

3)Floyd算法過程矩陣的計算—-十字交叉法

方法：兩條線，從左上角開始計算一直到右下角。

給出矩陣，其中矩陣A是鄰接矩陣，而矩陣Path記錄u,v兩點之間最短路徑所必須經(jīng)過的點。

延伸閱讀：

二、滾動數(shù)組

滾動數(shù)組是一種動態(tài)規(guī)劃中常見的降維優(yōu)化的方式，應(yīng)用廣泛（背包dp等），可以極大的減少空間復雜度。在我們求出的狀態(tài)轉(zhuǎn)移方程中，我們在更新f[k]層狀態(tài)的時候，用到f[k-1]層的值，f[k-2] f[k-3]層的值就直接廢棄了。所以我們大可讓名列前茅層的大小從n變成2,再進一步，我們在f[k]層更新f[k][i][j]的時候，f[k-1][i][k] 和 f[k-1][k][j] 我們?nèi)绻鼙ＷC，在更新k層另外一組路徑m->n的時候，不受前面更新過的f[k][i][j]的影響，就可以把名列前茅維度去掉了。我們現(xiàn)在去掉名列前茅個維度，寫成我們在代碼中的那樣，就是f[i][j] 依賴 f[i][k] + f[k][j] 我們在更新f[m][n]的時候，用到了f[m][k] + f[k][n] 假設(shè)f[i][j]的更新影響到了f[m][k] 或者 f[k][m] 即 {m=i,k=j} 或者 {k=i,n=j} 這時候有兩種情況，j和k是同一個點，或者i和k是同一個點，那么 f[i][j] = f[i][j] + f[j][j]，或者f[i][j] = f[i][i]+f[i][j] 這時候，我們所謂的“前面更新的點對”還是這兩個點本來的路徑，也就是說，少數(shù)兩種在某一層先更新的點，影響到后更新的點的情況，是完全合理的，所以說，我們即時把名列前茅維去掉，也滿足無后效性原則。因此可以用滾動數(shù)組優(yōu)化。優(yōu)化之后的狀態(tài)轉(zhuǎn)移方程即為：f[i][j] = min(f[i][j],f[i][k]+f[k][j])。