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算法過程是什么?

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直接相連。