Engineering Questions with Answers - Multiple Choice Questions

Home » MCQs » Chemical Engineering » Floyd-Warshall Algorithm MCQ’s

# Floyd-Warshall Algorithm MCQ’s

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.

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.

What is the running time of the Floyd Warshall Algorithm?

a) Big-oh(V)

b) Theta(V^{2})

c) Big-Oh(VE)

d) Theta(V^{3})

**
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(V^{3}).

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.

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(N^{3}) time is to assign a weight of 1 to each edge of E and then run the Floyd Warshall Algorithm.

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.

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.

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

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

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

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.

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.

The time taken to compute the transitive closure of a graph is Theta(n^{2}).

a) True

b) False

**
View Answer**

Answer: b

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

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

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.

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

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.

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