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

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

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

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

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

核心思路編輯

1、路徑矩陣

通過一個(gè)圖的權(quán)值矩陣求出它的每?jī)牲c(diǎn)間的最短路徑矩陣。

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

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

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

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

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

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

算法過程編輯

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

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

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

時(shí)間復(fù)雜度與空間復(fù)雜度編輯

時(shí)間復(fù)雜度:O(n^3)；

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

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

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

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

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