Floyd算法又稱為弗洛伊德算法，插點法，是壹種用於尋找給定的加權圖中頂點間最短路徑的算法。
算法過程:
把圖用鄰接距陣G表示出來，如果從Vi到Vj有路可達，則G[i,j]=d，d表示該路的長度；否則G[i,j]=空值。
定義壹個距陣D用來記錄所插入點的信息，D[i,j]表示從Vi到Vj需要經過的點，初始化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的路徑。根據D，假如D(5,1)=3則說明從V5到V1經過V3，路徑為{V5,V3,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。
Floyd算法（Floyd-Warshall algorithm）又稱為弗洛伊德算法、插點法，是解決給定的加權圖中頂點間的最短路徑的壹種算法，可以正確處理有向圖或負權的最短路徑問題，同時也被用於計算有向圖的傳遞閉包。該算法名稱以創始人之壹、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。
核心思路
通過壹個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。
從圖的帶權鄰接矩陣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)為圖的距離矩陣，同時還可引入壹個後繼節點矩陣path來記錄兩點間的最短路徑。
采用的是松弛技術，對在i和j之間的所有其他點進行壹次松弛。所以時間復雜度為O(n^3);
其狀態轉移方程如下：map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}
map[i,j]表示i到j的最短距離，K是窮舉，map[n,n]初值應該為0，或者按照題目意思來做。
當然，如果這條路沒有通的話，還必須特殊處理，比如沒有map[i,k]這條路。