Floyd-Warshall Algorithm Multiple choice Questions and Answers (MCQs)

Click on any option to know the CORRECT ANSWERS

 Question 1
Floyd Warshall's Algorithm is used for solving .....
 A All pair shortest path problems B Single Source shortest path problems C Network flow problems D Sorting problems

Question 1 Explanation:
Floyd Warshall's Algorithm is used for solving all pair shortest path problems. It means the algorithm is used for finding the shortest paths between all pairs of vertices in a graph.

 Question 2
Floyd Warshall's Algorithm can be applied on .....
 A Undirected and unweighted graphs B Undirected graphs C Directed graphs D Acyclic graphs

Question 2 Explanation:
Floyd Warshall Algorithm can be applied in directed graphs. From a given directed graph, an adjacency matrix is framed and then all pair shortest path is computed by the Floyd Warshall Algorithm.

 Question 3
What is the running time of the Floyd Warshall Algorithm?
 A Big-oh(V) B Theta(V2) C Big-Oh(VE) D Theta(V3)

Question 3 Explanation:
The running time of the Floyd Warshall algorithm is determined by the triply nested for loops. Since each execution of the for loop takes O(1) time, the algorithm runs in time Theta(V3).

 Question 4
What approach is being followed in Floyd Warshall Algorithm?
 A Greedy technique B Dynamic Programming C Linear Programming D Backtracking

Question 4 Explanation:
Floyd Warshall Algorithm follows dynamic programming approach because the all pair shortest paths are computed in bottom up manner.

 Question 5
Floyd Warshall Algorithm can be used for finding .....
 A Single source shortest path B Topological sort C Minimum spanning tree D Transitive closure