UTpaper

Free mock tests & test series

Question 21Asked in UGC NET Computer Science, December 2015 (Paper II & III, Selected Questions)

Floyd–Warshall algorithm utilizes ............. to solve the all-pairs shortest paths problem on a directed graph in .............. time.

  1. AGreedy algorithm, Θ(V³)
  2. BGreedy algorithm, Θ log n(V²lgn)
  3. CDynamic programming, Θ(V³)
  4. DDynamic programming, Θ log n(V² lgn)
Show answerHide answer

Correct answer: (C) Dynamic programming, Θ(V³)

Explanation

The Floyd–Warshall algorithm uses dynamic programming and compares all possible paths through the graph between each pair of vertices. It does this with Θ(|V|³) comparisons.

From UGC NET Computer Science PYQ, December 2015 (Paper II & III, Selected Questions)

This is question 21 of UGC NET Computer Science PYQ, December 2015 (Paper II & III, Selected Questions). 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.