|
floyd 算法是基于DP（動態(tài)規(guī)劃的一種算法），用于求每對頂點之間的最短路。
floyd 算法是 三層 for 循環(huán) ，復(fù)雜度是O(v^3) ,并且 隱藏在 O（v^3）下的常數(shù)也是非常小
算法介紹：
- 它需要用鄰接矩陣來儲存邊
- 從任意一條單邊路徑開始。所有兩點之間的距離是邊的權(quán)，如果兩點之間沒有邊相連，邊權(quán)就是無窮大。
- 對于每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。這種方法做松弛技術(shù)。松弛技術(shù)是三角關(guān)系 實質(zhì)就是 ： d(s,u)= min(d(s,u), d(s,v)+d(v,u) ) 。d(s,u) 表示從s點到 u 點的路徑長度。。。也就是如果找到一條比當前路徑更短的路徑長度，就更新當前的路徑長度。。
這個算法通過考慮最佳子路徑來得到最佳路徑。這個算法很容易實現(xiàn)，只要幾行。
dp狀態(tài)轉(zhuǎn)移的方程是 ： dp[k,i,j]=min(dp[k-1,i,j],dp[k-1,i,k]+dp[k-1,k,j])
- for(int k =1 ; k <= n ; k ++ ){
-
- for(int i =1 ; i<= n ; i++){
-
- for(int j =1 ;j<=n;j++){
-
- dp[k][ i ][ j ]= min( dp[k-1][ i ][ j ],dp[k-1][ i ][ k ]+dp[k-1][ k ][ j ] );
-
- }
-
- }
-
- }
|
