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
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
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
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).
4. What approach is being followed in Floyd Warshall Algorithm?
a) Greedy technique
b) Dynamic Programming
c) Linear Programming
d) Backtracking
View Answer
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
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
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
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.
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
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.
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
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
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
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
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?
a) 3
b) 2
c) 10
d) -3
View Answer
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?
a) 2
b) 0
c) 1
d) 3
View Answer
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
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.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Check Design and Analysis of Algorithms Books
- Practice Data Structure MCQ
- Apply for Computer Science Internship
- Practice Programming MCQs
- Check Programming Books
