Data Structures & Algorithms Multiple Choice Questions 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
Answer: a
Clarification: 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
Answer: c
Clarification: 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)
Answer: d
Clarification: 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
Answer: b
Clarification: 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
Answer: d
Clarification: 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
Answer: b
Clarification: 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
Answer: a
Clarification: 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
Answer: d
Clarification: 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))
Answer: c
Clarification: 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
Answer: b
Clarification: 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
Answer: a
Clarification: 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
Answer: b
Clarification: 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. 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))
Answer: b
Clarification: 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)).