UTpaper

Free mock tests & test series

Question 17Asked in Bihar STET Paper 2 Computer Science (Class 11-12), 12 Sep 2023, Shift 2

The Floyd-Warshall algorithm is a popular method for solving the All-Pair Shortest Paths problem. What is the time complexity of the Floyd-Warshall…

The Floyd-Warshall algorithm is a popular method for solving the All-Pair Shortest Paths problem. What is the time complexity of the Floyd-Warshall algorithm for a graph with "n" vertices?
  1. AO(n)
  2. BO(n log n)
  3. CO(n^2)
  4. DO(n^3)
Show answerHide answer

Correct answer: (D) O(n^3)

Explanation

Floyd-Warshall runs three nested loops over k, i and j, each from 1 to n, so it takes O(n³) time.

From Bihar STET Paper 2 Computer Science (Class 11-12) PYQ, 12 Sep 2023, Shift 2

This is question 17 of Bihar STET Paper 2 Computer Science (Class 11-12) PYQ, 12 Sep 2023, Shift 2. See all questions of this paper with answers, or attempt the paper as a timed online test to get your score and all-India rank.