floyd 算法是基于DP（動(dòng)態(tài)規(guī)劃的一種算法），用于求每對(duì)頂點(diǎn)之間的最短路。

floyd 算法是 三層 for 循環(huán) ，復(fù)雜度是O(v^3) ,并且 隱藏在 O（v^3）下的常數(shù)也是非常小

算法介紹：

• 它需要用鄰接矩陣來(lái)儲(chǔ)存邊
  
• 從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒(méi)有邊相連，邊權(quán)就是無(wú)窮大。
• 對(duì)于每一對(duì)頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。這種方法做松弛技術(shù)。松弛技術(shù)是三角關(guān)系     實(shí)質(zhì)就是 ：   d(s,u)= min(d(s,u), d(s,v)+d(v,u) )   。d(s,u)  表示從s點(diǎn)到 u 點(diǎn)的路徑長(zhǎng)度。。。也就是如果找到一條比當(dāng)前路徑更短的路徑長(zhǎng)度，就更新當(dāng)前的路徑長(zhǎng)度。。

這個(gè)算法通過(guò)考慮最佳子路徑來(lái)得到最佳路徑。這個(gè)算法很容易實(shí)現(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])