Floyd-Warshall演算法維基百科,自由的 encyclopedia Floyd-Warshall演算法(英語:Floyd-Warshall algorithm),中文亦稱弗洛伊德演算法或佛洛依德演算法[1],是解決任意兩點間的最短路徑的一種演算法[2],可以正確處理有向圖或負權(但不可存在負權迴路)的最短路徑問題,同時也被用於計算有向圖的遞移閉包[3]。 Quick Facts Floyd-Warshall演算法, 概況 ...Floyd-Warshall演算法概況類別全域最短路徑問題(適用於帶權圖)資料結構圖複雜度平均時間複雜度 Θ ( | V | 3 ) {\displaystyle \Theta (|V|^{3})} 最壞時間複雜度 O ( | V | 3 ) {\displaystyle O(|V|^{3})} 最佳時間複雜度 Ω ( | V | 3 ) {\displaystyle \Omega (|V|^{3})} 空間複雜度 Θ ( | V | 2 ) {\displaystyle \Theta (|V|^{2})} 相關變數的定義 V {\displaystyle V} 點集Close Floyd-Warshall演算法的時間複雜度為 O ( | V | 3 ) {\displaystyle O(|V|^{3})} [4],空間複雜度為 O ( | V | 2 ) {\displaystyle O(|V|^{2})} ,其中 V {\displaystyle V} 是點集。
Floyd-Warshall演算法(英語:Floyd-Warshall algorithm),中文亦稱弗洛伊德演算法或佛洛依德演算法[1],是解決任意兩點間的最短路徑的一種演算法[2],可以正確處理有向圖或負權(但不可存在負權迴路)的最短路徑問題,同時也被用於計算有向圖的遞移閉包[3]。 Quick Facts Floyd-Warshall演算法, 概況 ...Floyd-Warshall演算法概況類別全域最短路徑問題(適用於帶權圖)資料結構圖複雜度平均時間複雜度 Θ ( | V | 3 ) {\displaystyle \Theta (|V|^{3})} 最壞時間複雜度 O ( | V | 3 ) {\displaystyle O(|V|^{3})} 最佳時間複雜度 Ω ( | V | 3 ) {\displaystyle \Omega (|V|^{3})} 空間複雜度 Θ ( | V | 2 ) {\displaystyle \Theta (|V|^{2})} 相關變數的定義 V {\displaystyle V} 點集Close Floyd-Warshall演算法的時間複雜度為 O ( | V | 3 ) {\displaystyle O(|V|^{3})} [4],空間複雜度為 O ( | V | 2 ) {\displaystyle O(|V|^{2})} ,其中 V {\displaystyle V} 是點集。