floyd算法原理是一種利用動態(tài)規(guī)劃的思想尋找給定的加權圖中多源點之間最短路徑的算法，與Dijkstra算法類似，同樣一種在具有正或負邊緣權重的加權圖中找到最短路徑的算法。

Floyd算法又稱為插點法，是一種利用動態(tài)規(guī)劃的思想尋找給定的加權圖中多源點之間最短路徑的算法，與Dijkstra算法類似。該算法名稱以創(chuàng)始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名

在計算機科學中，F(xiàn)loyd-Warshall算法是一種在具有正或負邊緣權重（但沒有負周期）的加權圖中找到最短路徑的算法。算法的單個執(zhí)行將找到所有頂點對之間的最短路徑的長度（加權）。 雖然它不返回路徑本身的細節(jié)，但是可以通過對算法的簡單修改來重建路徑。 該算法的版本也可用于查找關系R的傳遞閉包，或（與Schulze投票系統(tǒng)相關）在加權圖中所有頂點對之間的最寬路徑。

Floyd-Warshall算法是動態(tài)規(guī)劃的一個例子，并在1962年由Robert Floyd以其當前公認的形式出版。然而，它基本上與Bernard Roy在1959年先前發(fā)表的算法和1962年的Stephen Warshall中找到圖形的傳遞閉包基本相同，并且與Kleene的算法密切相關 在1956年）用于將確定性有限自動機轉換為正則表達式。算法作為三個嵌套for循環(huán)的現(xiàn)代公式首先由Peter Ingerman在1962年描述。

該算法也稱為Floyd算法，Roy-Warshall算法，Roy-Floyd算法或WFI算法。

核心思路編輯

1、路徑矩陣

通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。

從圖的帶權鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1)；又用同樣地公式由D(1)構造出D(2)；……；最后又用同樣的公式由D(n-1)構造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣path來記錄兩點間的最短路徑。

采用松弛技術（松弛操作），對在i和j之間的所有其他點進行一次松弛。所以時間復雜度為O(n^3);

2、狀態(tài)轉移方程

其狀態(tài)轉移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；

map[i,j]表示i到j的最短距離，K是窮舉i,j的斷點，map[n,n]初值應該為0，或者按照題目意思來做。

當然，如果這條路沒有通的話，還必須特殊處理，比如沒有map[i,k]這條路。

算法過程編輯

1，從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，如果兩點之間沒有邊相連，則權為無窮大。

2，對于每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比已知的路徑更短。如果是更新它。

把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達，則G[i][j]=d，d表示該路的長度；否則G[i][j]=無窮大。定義一個矩陣D用來記錄所插入點的信息，D[i][j]表示從Vi到Vj需要經(jīng)過的點，初始化D[i][j]=j。把各個頂點插入圖中，比較插點后的距離與原來的距離，G[i][j] = min( G[i][j], G[i][k]+G[k][j] )，如果G[i][j]的值變小，則D[i][j]=k。在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。

比如，要尋找從V5到V1的路徑。根據(jù)D，假如D(5,1)=3則說明從V5到V1經(jīng)過V3，路徑為{V5,V3,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。

時間復雜度與空間復雜度編輯

時間復雜度:O(n^3)；

空間復雜度:O(n^2)

優(yōu)缺點分析編輯

Floyd算法適用于APSP(All Pairs Shortest Paths，多源最短路徑)，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳，邊權可正可負。此算法簡單有效，由于三重循環(huán)結構緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法，也要高于執(zhí)行|V|次SPFA算法。

優(yōu)點：容易理解，可以算出任意兩個節(jié)點之間的最短距離，代碼編寫簡單。

缺點：時間復雜度比較高，不適合計算大量數(shù)據(jù)。