Engineering Questions with Answers - Multiple Choice Questions

Floyd-Warshall Algorithm MCQ’s

1 - Question

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

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 - Question

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

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 - Question

What is the running time of the Floyd Warshall Algorithm?
a) Big-oh(V)
b) Theta(V2)
c) Big-Oh(VE)
d) Theta(V3)

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 - Question

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

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

5 - Question

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

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 - Question

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

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 - Question

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

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 - Question

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

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

9 - Question

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

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 - Question

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

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 - Question

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

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

12 - Question

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

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 - Question

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

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 - Question

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

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 - Question

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