Floyd算法又稱為弗洛伊德算法,插點(diǎn)法,是一種用于尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的算法.
通過(guò)一個(gè)圖的權(quán)值矩陣求出它的每?jī)牲c(diǎn)間的最短路徑矩陣. 　　
從圖的帶權(quán)鄰接矩陣A=[a(i,j)] n×n開(kāi)始,遞歸地進(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來(lái)記錄兩點(diǎn)間的最短路徑. 　　
采用的是(松弛技術(shù)),對(duì)在i和j之間的所有其他點(diǎn)進(jìn)行一次松弛.所以時(shí)間復(fù)雜度為O(n^3); 　　其狀態(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,或者按照題目意思來(lái)做. 　　
當(dāng)然,如果這條路沒(méi)有通的話,還必須特殊處理,比如沒(méi)有map[i,k]這條路