alleryStart learning →The running time and space of Floyd-Warshall on a graph with V vertices and E edges is
AO(V + E) time, O(V) space
BO(V³) time, O(V²) space
CO(E log V) time, O(E) space
DO(V² log V) time, O(V²) space
Answer & Solution
Correct answer: B. O(V³) time, O(V²) space
Floyd-Warshall uses a V × V distance matrix updated by three nested loops, giving O(V³) time and O(V²) space.
The space holds the d[i][j] table.
Time is independent of E because every (i, j) pair is examined regardless of whether an edge exists.
The other options describe BFS or Dijkstra variants.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.