floyd warshall 运行 边的时间复杂度
floyd warshall running time complexity in terms of edges
表示Floyd-Warshall算法的运行时间Θ()
图 G(V, E) 的所有对最短路径问题：
一世。就 G 中的顶点 V 的数量而言。
二.就稠密图 G 中的边 E 的数量而言。
三.就稀疏图G的边数E而言。
第 i 个。它将是 O(V^3) 。 （ 如果我错了纠正我 ）。
对于数字 ii 和 iii。我找不到办法做到这一点。两者仍然是 O(E^3) 吗？
在 Floyd-Warshall 算法的标准实现中，有三个嵌套循环 运行 通过图的顶点。如您所说，这给出了 O(V^3) 的时间复杂度，并且与 E.
的大小无关
如果您将稠密图定义为 E ~ V^2，将稀疏图定义为 E ~ V，则 (ii) 和 (iii) 的答案将为 O(E^( 3/2)) 和 O(E^3) 分别。
表示Floyd-Warshall算法的运行时间Θ() 图 G(V, E) 的所有对最短路径问题： 一世。就 G 中的顶点 V 的数量而言。 二.就稠密图 G 中的边 E 的数量而言。 三.就稀疏图G的边数E而言。
第 i 个。它将是 O(V^3) 。 （ 如果我错了纠正我 ）。 对于数字 ii 和 iii。我找不到办法做到这一点。两者仍然是 O(E^3) 吗？
在 Floyd-Warshall 算法的标准实现中，有三个嵌套循环 运行 通过图的顶点。如您所说，这给出了 O(V^3) 的时间复杂度，并且与 E.
的大小无关如果您将稠密图定义为 E ~ V^2，将稀疏图定义为 E ~ V，则 (ii) 和 (iii) 的答案将为 O(E^( 3/2)) 和 O(E^3) 分别。