ExamCompetition Your Success, Our Mission
Login Register
Question discussion

What is the time complexity of the Floyd–Warshall algorithm for finding all-pairs shortest paths in a graph with V vertices?

2156Medium DSSSB TGT Computer Science 0 replies 1 views
0

What is the time complexity of the Floyd–Warshall algorithm for finding all-pairs shortest paths in a graph with V vertices?

  • AO(V²)
  • BO(V³)
  • CO(V² log V)
  • DO(V log V)
Correct answer: B

Explanation

The algorithm uses three nested loops over the V vertices (intermediate, source and destination), so it runs in O(V³) time.
Join the discussion Report an error

Discussion 0

Nobody has replied yet. Start the discussion!