來自某人博客,失效了去github看
github

看不懂 Floyd算法又稱為插點法，是一種利用動態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點之間最短路徑的算法，與Dijkstra算法類似。該算法名稱以創(chuàng)始人之一、1978年圖靈獎獲得者、斯坦福大學(xué)計算機(jī)科學(xué)系教授羅伯特·弗洛伊德命名。從圖的帶權(quán)鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進(jìn)行n次更新，即由矩陣D(0)=A，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；……；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j(luò)號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣path來記錄兩點間的最短路徑。采用松弛技術(shù)（松弛操作），對在i和j之間的所有其他點進(jìn)行一次松弛。所以時間復(fù)雜度為O(n^3)

---

知乎上有動態(tài)規(guī)劃的解釋，這里給出通俗易懂的解釋

開始算法之前，首先介紹一下這個算法是如何運行的，e[i][j]指的是從 i 到 j 的最短路，在初始化的時候，如果著兩條邊直接有路相連，那么直接賦值，如果沒有連接，那么就設(shè)為正無窮大，一般用一個比較大的數(shù)。然后每次比較 i 和 j 之間的中間點 k ，如果 i 到k 加上 k 到 j 的權(quán)值小于 i 直接到 j 那么 e[i][j]的值也就是 i 到 j 的最短路就變成了從e[i][k]+e[k][j]的值。

循環(huán)最外層證明

但是為什么要先枚舉k呢，為什么不能先枚舉 i 然后再枚舉 i 的中間點k，最后枚舉 j 呢，其實這是因為，i=1,j=2時，這時k分別取1,2,…,n，這時1到3，1到4，…，3到2，4到2，…的距離都不是某種意義上最短的，而這個新算法卻直接使用了他們，并且再也沒有回頭重新計算i到j(luò)的距離是否因為其他節(jié)點間距離的改變而更短，所以這樣算出來的值也就沒有什么意義。

如圖

在上面這個圖中枚舉i=A，j=B，然后循環(huán)，正確的A到B最小是3，然而你更新的是125,

因為最短那個不是只有一個中介點，所以就沒更新

因為你在枚舉下一個i之后，就不會再次回去了，所以說A,B之間的最短路就被定為了125，以后也會以e[i][j]=125去更新其他的點，所以說，k循環(huán)必須放在最外層，不然會有可能無法找到最優(yōu)值。

---

---

---

---

種一棵樹最好的時間是十年前，其次是現(xiàn)在。

總結(jié)

以上是生活随笔為你收集整理的算法笔记----Floyed的k循环在最外层详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。