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

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Floyd-Warshall Algorithm”.

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
View Answer

Answer: a
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.

2. Floyd Warshall’s Algorithm can be applied on __________
a) Undirected and unweighted graphs
b) Undirected graphs
c) Directed graphs
d) Acyclic graphs
View Answer

Answer: c
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.

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)
View Answer

Answer: d
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).
advertisement
advertisement

4. What approach is being followed in Floyd Warshall Algorithm?
a) Greedy technique
b) Dynamic Programming
c) Linear Programming
d) Backtracking
View Answer

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

5. Floyd Warshall Algorithm can be used for finding _____________
a) Single source shortest path
b) Topological sort
c) Minimum spanning tree
d) Transitive closure
View Answer

Answer: d
Explanation: One of the ways to compute the transitive closure of a graph in Theta(N3) time is to assign a weight of 1 to each edge of E and then run the Floyd Warshall Algorithm.

6. What procedure is being followed in Floyd Warshall Algorithm?
a) Top down
b) Bottom up
c) Big bang
d) Sandwich
View Answer

Answer: b
Explanation: Bottom up procedure is being used to compute the values of the matrix elements dij(k). The input is an n x n matrix. The procedure returns the matrix D(n) of the shortest path weights.

7. Floyd- Warshall algorithm was proposed by ____________
a) Robert Floyd and Stephen Warshall
b) Stephen Floyd and Robert Warshall
c) Bernad Floyd and Robert Warshall
d) Robert Floyd and Bernad Warshall
View Answer

Answer: a
Explanation: Floyd- Warshall Algorithm was proposed by Robert Floyd in the year 1962. The same algorithm was proposed by Stephen Warshall during the same year for finding the transitive closure of the graph.
advertisement

8. Who proposed the modern formulation of Floyd-Warshall Algorithm as three nested loops?
a) Robert Floyd
b) Stephen Warshall
c) Bernard Roy
d) Peter Ingerman
View Answer

Answer: d
Explanation: The modern formulation of Floyd-Warshall Algorithm as three nested for-loops was proposed by Peter Ingerman in the year 1962.

9. Complete the program.

advertisement
n=rows[W]
D(0)=W
for k=1 to n
     do for i=1 to n
          do for j=1 to n
                 do ________________________________
return D(n)

a) dij(k)=min(dij(k-1), dik(k-1) – dkj(k-1))
b) dij(k)=max(dij(k-1), dik(k-1) – dkj(k-1))
c) dij(k)=min(dij(k-1), dik(k-1) + dkj(k-1))
d) dij(k)=max(dij(k-1), dik(k-1) + dkj(k-1))
View Answer

Answer: c
Explanation: In order to compute the shortest path from vertex i to vertex j, we need to find the minimum of 2 values which are dij(k-1) and sum of dik(k-1) and dkj(k-1).

10. What happens when the value of k is 0 in the Floyd Warshall Algorithm?
a) 1 intermediate vertex
b) 0 intermediate vertex
c) N intermediate vertices
d) N-1 intermediate vertices
View Answer

Answer: b
Explanation: When k=0, a path from vertex i to vertex j has no intermediate vertices at all. Such a path has at most one edge and hence dij(0) = wij.

11. Using logical operator’s instead arithmetic operators saves time and space.
a) True
b) False
View Answer

Answer: a
Explanation: In computers, logical operations on single bit values execute faster than arithmetic operations on integer words of data.

12. The time taken to compute the transitive closure of a graph is Theta(n2).
a) True
b) False
View Answer

Answer: b
Explanation: The time taken to compute the transitive closure of a graph is Theta(n3). Transitive closure can be computed by assigning weight of 1 to each edge and by running Floyd Warshall Algorithm.

13. In the given graph, what is the minimum cost to travel from vertex 1 to vertex 3?
The minimum cost to travel from vertex 1 to vertex 3 is -3
a) 3
b) 2
c) 10
d) -3
View Answer

Answer: d
Explanation: The minimum cost required to travel from node 1 to node 5 is -3.
1-5, cost is -4
5-4, cost is 6
4-3, cost is -5
Hence total cost is -4 + 6 + -5 = -3.

14. In the given graph, how many intermediate vertices are required to travel from node a to node e at a minimum cost?
Intermediate vertices are required to travel from node a to node e at a minimum cost of 1
a) 2
b) 0
c) 1
d) 3
View Answer

Answer: c
Explanation: The minimum cost to travel from node a to node e is 1 by passing via nodes b and c.
a-b, cost 5
b-c, cost 3
c-e, cost -7
Hence the total cost is 1.

15. What is the formula to compute the transitive closure of a graph?
a) tij(k) = tij(k-1) AND (tik(k-1) OR tkj(k-1))
b) tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1))
c) tij(k) = tij(k-1) AND (tik(k-1) AND tkj(k-1))
d) tij(k) = tij(k-1) OR (tik(k-1) OR tkj(k-1))
View Answer

Answer: b
Explanation: Transitive closure of a graph can be computed by using Floyd Warshall algorithm. This method involves substitution of logical operations (logical OR and logical AND) for arithmetic operations min and + in Floyd Warshall Algorithm.
Floyd Warshall Algorithm: dij(k)=min(dij(k-1), dik(k-1) + dkj(k-1))
Transitive closure: tij(k)= tij(k-1) OR (tik(k-1) AND tkj(k-1)).

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.