# Shortest Path Algorithms MCQ

1. Dijkstra’s Algorithm is used to solve _________ problems.

a) All pair’s shortest path

b) Single source shortest path

c) Network flow

d) Sorting

Answer: b

Dijkstra’s Algorithm is used for solving single source shortest path problems. In this algorithm, a single node is fixed as a source node and the shortest paths from this node to all other nodes in the graph are found.

2. Which of the following is the most commonly used data structure for implementing Dijkstra’s Algorithm?

a) Max priority queue

b) Stack

c) Circular queue

d) Min priority queue

Answer: d

A minimum priority queue is the most commonly used data structure for implementing Dijkstra’s Algorithm because the required operations to be performed in Dijkstra’s Algorithm match with the specialty of a minimum priority queue.

3. What is the time complexity of Dijkstra’s algorithm?

a) O(N)

b) O(N^{3})

c) O(N^{2})

d) O(logN)

Answer: c

The time complexity of Dijkstra’s algorithm is O(N^{2}) because of the use of doubly nested for loops. It depends on how the table is manipulated.

4. Dijkstra’s Algorithm cannot be applied on ___________

a) Directed and weighted graphs

b) Graphs having negative weight function

c) Unweighted graphs

d) Undirected and unweighted graphs

Answer: b

Dijkstra’s Algorithm cannot be applied on graphs having a negative weight function because the calculation of the cost to reach a destination node from the source node becomes complex.

6. How many priority queue operations are involved in Dijkstra’s Algorithm?

a) 1

b) 3

c) 2

d) 4

Answer: b

The number of priority queue operations involved is 3. They are insert, extract-min, and decrease key.

7. How many times the insert and extract min operations are invoked per vertex?

a) 1

b) 2

c) 3

d) 0

Answer: a

Insert and extract min operations are invoked only once per vertex because each vertex is added only once to the set and each edge in the adjacency list is examined only once during the course of the algorithm.

8. The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be equal to ___________

a) Total number of vertices

b) Total number of edges

c) Number of vertices – 1

d) Number of edges – 1

Answer: b

If the total number of edges in all adjacency lists is E, then there will be a total of E number of iterations, hence there will be a total of at most E decrease key operations.

9. What is running time of Dijkstra’s algorithm using Binary min- heap method?

a) O(V)

b) O(VlogV)

c) O(E)

d) O(ElogV)

Answer: d

The time required to build a binary min-heap is O(V). Each decrease key operation takes O(logV) and there are still at most E such operations. Hence total running time is O(ElogV).

10. The running time of the Bellmann Ford algorithm is higher than that of Dijkstra’s Algorithm.

a) True

b) False

Answer: a

The number of iterations involved in the Bellmann Ford Algorithm is more than that of Dijkstra’s Algorithm.

11. Dijkstra’s Algorithm runs on a weighted, directed graph G={V, E} with non-negative weight function w and source s, terminates with d[u]=delta(s,u) for all vertices u in V.

a) True

b) False

Answer: a

The equality d[u]=delta(s,u) holds good when vertex u is added to set S and this equality is maintained thereafter by the upper bound property.

13. Consider the following graph.

If b is the source vertex, what is the minimum cost to reach the f vertex?

a) 8

b) 9

c) 4

d) 6

Answer: d

The minimum cost to reach f vertex from b vertex is 6 by having vertices g and e as intermediates.

b to g, the cost is 1

g to e, the cost is 4

e to f, the cost is 1

hence the total cost is 1+4+1=6.

14. In the given graph, identify the shortest path having minimum cost to reach vertex E if A is the source vertex.

a) a-b-e

b) a-c-e

c) a-c-d-e

d) a-c-d-b-e

Answer: b

The minimum cost required to travel from vertex A to E is via vertex C

A to C, cost= 3

C to E, cost= 2

Hence the total cost is 5.

15. Dijkstra’s Algorithm is the prime example for ___________

a) Greedy algorithm

b) Branch and bound

c) Back tracking

d) Dynamic programming

Answer: a

Dijkstra’s Algorithm is the prime example of greedy algorithms because greedy algorithms generally solve a problem in stages by doing what appears to be the best thing at each stage.

1. The Bellmann Ford algorithm returns _______ value.

a) Boolean

b) Integer

c) String

d) Double

Answer: a

The Bellmann Ford algorithm returns a Boolean value whether there is a negative weight cycle that is reachable from the source.

2. Bellmann ford algorithm provides solution for ____________ problems.

a) All pair’s shortest path

b) Sorting

c) Network flow

d) Single source shortest path

Answer: d

Bellmann ford algorithm is used for finding solutions for single source shortest path problems. If the graph has no negative cycles that are reachable from the source then the algorithm produces the shortest paths and their weights.

3. Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not.

a) True

b) False

Answer: a

Bellmann Ford algorithm returns true if the graph does not have any negative weight cycles and returns false when the graph has negative weight cycles.

4. How many solution/solutions are available for a graph having a negative weight cycle?

a) One solution

b) Two solutions

c) No solution

d) Infinite solutions

Answer: c

If the graph has any negative weight cycle then the algorithm indicates that no solution exists for that graph.

5. What is the running time of the Bellmann Ford Algorithm?

a) O(V)

b) O(V2)

c) O(ElogV)

d) O(VE)

Answer: d

Bellmann Ford algorithm runs in time O(VE) since the initialization takes O(V) for each of V-1 passes and the for loop in the algorithm takes O(E) time. Hence the total time taken by the algorithm is O(VE).

6. How many times does the for loop in the Bellmann Ford Algorithm get executed?

a) V times

b) V-1

c) E

d) E-1

Answer: b

The for loop in the Bellmann Ford Algorithm gets executed for V-1 times. After making V-1 passes, the algorithm checks for a negative weight cycle and returns an appropriate boolean value.

7. Dijkstra’s Algorithm is more efficient than Bellmann Ford’s Algorithm.

a) True

b) False

Answer: a

The running time of the Bellmann Ford Algorithm is O(VE) whereas Dijkstra’s Algorithm has a running time of only O(V^{2}).

9. What is the basic principle behind Bellmann Ford Algorithm?

a) Interpolation

b) Extrapolation

c) Regression

d) Relaxation

Answer: d

Relaxation methods are also called iterative methods in which an approximation to the correct distance is replaced progressively by more accurate values till an optimum solution is found.

10. Bellmann Ford Algorithm can be applied for __________

a) Undirected and weighted graphs

b) Undirected and unweighted graphs

c) Directed and weighted graphs

d) All directed graphs

Answer: c

Bellmann Ford Algorithm can be applied for all directed and weighted graphs. The weight function in the graph may either be positive or negative.

11. Bellmann Ford algorithm was first proposed by ________

a) Richard Bellmann

b) Alfonso Shimbe

c) Lester Ford Jr

d) Edward F. Moore

Answer: b

Alfonso Shimbe proposed the Bellmann Ford algorithm in the year 1955. Later it was published by Richard Bellmann in 1957 and Lester Ford Jr in the year 1956. Hence it is called Bellmann Ford Algorithm.

12. Consider the following graph. What is the minimum cost to travel from node A to node C?

a) 5

b) 2

c) 1

d) 3

Answer: b

The minimum cost to travel from node A to node C is 2.

A-D, cost=1

D-B, cost=-2

B-C cost=3

Hence the total cost is 2.

13. In the given graph, identify the path that has minimum cost to travel from node a to node f.

a) a-b-c-f

b) a-d-e-f

c) a-d-b-c-f

d) a-d-b-c-e-f

Answer: d

The minimum cost taken by the path a-d-b-c-e-f is 4.

a-d, cost=2

d-b, cost=-2

b-c, cost=1

c-e, cost= 2

e-f, cost=1

Hence the total cost is 4.

14. Bellmann Ford Algorithm is an example for ____________

a) Dynamic Programming

b) Greedy Algorithms

c) Linear Programming

d) Branch and Bound

Answer: a

In Bellmann Ford Algorithm the shortest paths are calculated in a bottom-up manner which is similar to other dynamic programming problems.

15. A graph is said to have a negative weight cycle when?

a) The graph has 1 negative weighted edge

b) The graph has a cycle

c) The total weight of the graph is negative

d) The graph has 1 or more negative weighted edges

Answer: c

When the total weight of the graph sums up to a negative number then the graph is said to have a negative weight cycle. Bellmann Ford Algorithm provides no solution for such graphs.

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

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

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

Answer: d

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

4. What approach is being followed in Floyd Warshall Algorithm?

a) Greedy technique

b) Dynamic Programming

c) Linear Programming

d) Backtracking

Answer: b

Floyd Warshall Algorithm follows a dynamic programming approach because they all pair shortest paths are computed in a 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

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.

6. What procedure is being followed in Floyd Warshall Algorithm?

a) Top-down

b) Bottom-up

c) Big bang

d) Sandwich

Answer: b

The 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

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 the Floyd-Warshall Algorithm as three nested loops?

a) Robert Floyd

b) Stephen Warshall

c) Bernard Roy

d) Peter Ingerman

Answer: d

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

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

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 operators instead arithmetic operators saves time and space.

a) True

b) False

Answer: a

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

a) True

b) False

Answer: a

The time taken to compute the transitive closure of a graph is Theta(n^{3}). Transitive closure can be computed by assigning a 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

The transitive closure of a graph can be computed by using the Floyd Warshall algorithm.

This method involves the substitution of logical operations (logical OR and logical AND) for arithmetic operations min and + in the 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)).

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

Answer. D

The minimum cost required to travel from node 1 to node 5 is -3.

1-5, the cost is -4

5-4, the cost is 6

4-3, the cost is -5

Hence total cost is -4 + 6 + -5 = -3.

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

Answer. C

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.