一、floyd算法為什么要用鄰接矩陣實現而不用鄰接表
floyd算法要用鄰接矩陣實現而不用鄰接表是因為需要O(1)時間查詢任意兩個頂點的邊權值,在這一句中:d(i, j) = d(i, k) + d(k, j)。Floyd 算法是一個基于「貪心」、「動態(tài)規(guī)劃」求一個圖中 所有點到所有點 最短路徑的算法,時間復雜度 O(n3)。
1)算法思想原理:
Floyd算法是一個經典的動態(tài)規(guī)劃算法。用通俗的語言來描述的話,首先我們的目標是尋找從點i到點j的最短路徑。從動態(tài)規(guī)劃的角度看問題,我們需要為這個目標重新做一個詮釋(這個詮釋正是動態(tài)規(guī)劃最富創(chuàng)造力的精華所在)
從任意節(jié)點i到任意節(jié)點j的最短路徑不外乎2種可能,1是直接從i到j,2是從i經過若干個節(jié)點k到j。所以,我們假設Dis(i,j)為節(jié)點u到節(jié)點v的最短路徑的距離,對于每一個節(jié)點k,我們檢查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,證明從i到k再到j的路徑比i直接到j的路徑短,我們便設置Dis(i,j) = Dis(i,k) + Dis(k,j),這樣一來,當我們遍歷完所有節(jié)點k,Dis(i,j)中記錄的便是i到j的最短路徑的距離。
2)算法描述:
a.從任意一條單邊路徑開始。所有兩點之間的距離是邊的權,如果兩點之間沒有邊相連,則權為無窮大。
b.對于每一對頂點 u 和 v,看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。
3)Floyd算法過程矩陣的計算—-十字交叉法
方法:兩條線,從左上角開始計算一直到右下角。
給出矩陣,其中矩陣A是鄰接矩陣,而矩陣Path記錄u,v兩點之間最短路徑所必須經過的點。
延伸閱讀:
二、滾動數組
滾動數組是一種動態(tài)規(guī)劃中常見的降維優(yōu)化的方式,應用廣泛(背包dp等),可以極大的減少空間復雜度。在我們求出的狀態(tài)轉移方程中,我們在更新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] 我們如果能保證,在更新k層另外一組路徑m->n的時候,不受前面更新過的f[k][i][j]的影響,就可以把名列前茅維度去掉了。我們現在去掉名列前茅個維度,寫成我們在代碼中的那樣,就是f[i][j] 依賴 f[i][k] + f[k][j] 我們在更新f[m][n]的時候,用到了f[m][k] + f[k][n] 假設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] 這時候,我們所謂的“前面更新的點對”還是這兩個點本來的路徑,也就是說,少數兩種在某一層先更新的點,影響到后更新的點的情況,是完全合理的,所以說,我們即時把名列前茅維去掉,也滿足無后效性原則。因此可以用滾動數組優(yōu)化。優(yōu)化之后的狀態(tài)轉移方程即為:f[i][j] = min(f[i][j],f[i][k]+f[k][j])。