一、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ī)劃」求一個圖中 所有點到所有點 最短路徑的算法,時間復(fù)雜度 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等),可以極大的減少空間復(fù)雜度。在我們求出的狀態(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)绻鼙WC,在更新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])。