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} 是点集。