[圖]最短路徑-Floyd演算法

• 2020 年 3 月 12 日
• 筆記

<!–more–> > Floyd演算法（Floyd-Warshall algorithm）又稱為插點法，是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的演算法，與Dijkstra演算法類似。該演算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學電腦科學系教授羅伯特·弗洛伊德命名。 -來自百度百科 前一篇文章：[第六章 圖-Dijkstra演算法](https://study.sqdxwz.com/index.php/archives/13/) 我們已經學習過了單源最短路徑求解方法，這次我們來學習所有頂點間（任意兩點間）的最短路徑求解方法-Floyd演算法。 對於求解任意兩點最短路徑的方式，我們也可以採用簡單暴力將Dijkstra演算法循環n遍（假設存在有n個頂點），也是可以求解任意兩點間距離的，但是人類社會之所以會進步，難道僅僅是會使用筷子？還是好好學習更先進的演算法-Floyd演算法吧！ **註：**採用此暴力的時間複雜度為：O(n^3）。

# Floyd演算法 開始之前我們需要了解到的一些知識點： 1.稀疏的圖，採用n次Dijkstra比較出色； 稠密的圖，採用Floyd演算法比較好； 2.Floyd演算法可以處理帶負邊的圖； 3.同時也被用於計算有向圖的傳遞閉包； 4.Floyd-Warshall演算法的時間複雜度為O(n^3），空間複雜度為O(n^2）。 ## 1.演算法思路 1.初始化，設置一個n階方陣，令其對角線的元素為0，若存在<vi,vj>,則對應元素為權值，否則為∞（過程1其實就是建立一個[鄰接矩陣](https://baike.baidu.com/item/%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5/9796080?fr=aladdin)）； 2.逐步試著在原路徑中增加中間頂點，若加入中間頂點後路徑變短，則進行修改，否則，維持原值； 3.進行所有頂點的試探，直至進行全部循環，演算法結束。 ## 2.程式碼實現 “`python import numpy as np N = 4 M = 100 edge = np.mat([[0,2,6,4],[M,0,3,M],[7,M,0,1],[5,M,12,0]]) A = edge[:] path = np.zeros((N,N)) def Floyd(): for i in range(N): for j in range(N): if(edge[i,j] != M and edge[i,j] != 0): path[i][j] = i print('init:') print(A,'n',path) for a in range(N): for b in range(N): for c in range(N): if(A[b,a]+A[a,c]<A[b,c]): A[b,c] = A[b,a] + A[a,c] path[b][c] = path[a][c] print('result:') print(A,"n",path) if __name__ == "__main__": Floyd() “`