關(guān)于弗洛伊德算法優(yōu)點(diǎn)，弗洛伊德算法這個(gè)問題很多朋友還不知道，今天小六來為大家解答以上的問題，現(xiàn)在讓我們一起來看看吧！
1、通過一個(gè)圖的權(quán)值矩陣求出它的每?jī)牲c(diǎn)間的最短路徑矩陣。
2、從圖的帶權(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)。
3、矩陣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)間的最短路徑。
4、采用的是(松弛技術(shù))，對(duì)在i和j之間的所有其他點(diǎn)進(jìn)行一次松弛。
5、所以時(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，或者按照題目意思來做。
6、當(dāng)然，如果這條路沒有通的話，還必須特殊處理，比如沒有map[i,k]這條路。
本文分享完畢，希望對(duì)大家有所幫助。
標(biāo)簽：
免責(zé)聲明：本文由用戶上傳，如有侵權(quán)請(qǐng)聯(lián)系刪除！