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

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

1)算法思想原理：

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

從任意節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的最短路徑不外乎2種可能，1是直接從i到j(luò)，2是從i經(jīng)過若干個(gè)節(jié)點(diǎn)k到j(luò)。所以，我們假設(shè)Dis(i,j)為節(jié)點(diǎn)u到節(jié)點(diǎn)v的最短路徑的距離，對于每一個(gè)節(jié)點(diǎn)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)，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn)k，Dis(i,j)中記錄的便是i到j(luò)的最短路徑的距離。

2)算法描述：

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

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

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

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

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

延伸閱讀：

二、滾動(dòng)數(shù)組

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