摘要： 今天小編蘇蘇來為大家解答以上的問題。弗洛伊德算法和迪杰斯特拉算法的區別，弗洛伊德算法相信很多小伙伴還不知道,現在讓我們一起來看看吧！1、通過一個圖的權值矩陣求出它的每兩點間的最短路...

今天小編蘇蘇來為大家解答以上的問題。弗洛伊德算法和迪杰斯特拉算法的區別，弗洛伊德算法相信很多小伙伴還不知道,現在讓我們一起來看看吧！

1、通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。

2、從圖的帶權鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1);又用同樣地公式由D(1)構造出D(2);……;最后又用同樣的公式由D(n-1)構造出矩陣D(n)。

3、矩陣D(n)的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節點矩陣path來記錄兩點間的最短路徑。

4、采用的是(松弛技術)，對在i和j之間的所有其他點進行一次松弛。

5、所以時間復雜度為O(n^3);其狀態轉移方程如下: map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}map[i,j]表示i到j的最短距離K是窮舉i,j的斷點map[n,n]初值應該為0，或者按照題目意思來做。

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

本文就為大家分享到這里，希望小伙伴們會喜歡。