floyd warshall running time complexity in terms of edges

Question

Express the running time Θ() of the Floyd-Warshall algorithm for the all pairs shortest path problem for a graph G(V, E): i. In terms of the number of vertices V in G. ii. In terms of the number of edges E in a dense graph G. iii. In terms of the number of edges E in a sparse graph G.

for number i. it would be O(V^3) . ( correct me if im wrong ). for number ii and iii. I could not find a way to do it. is it still O(E^3) for both?

Answer 1

In the standard implementation of Floyd-Warshall algorithm, there are three nested loops that run through the vertices of the graph. This gives a time complexity of O(V^3) as you said, and is independent of the size of E.

If you define a dense graph to be one where E ~ V^2 and a sparse graph to be one where E ~ V, then your answers to (ii) and (iii) will be O(E^(3/2)) and O(E^3) respectively.