Dijkstra’s Algorithm Questions and Answers

Dijkstra’s Algorithm Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Dijkstra’s Algorithm”.

1. Dijkstra’s Algorithm run 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

Explanation: When vertex u is added to set S, the equivalence d[u]=delta(s,u) is true, and the upper bound property maintains this equality.
2. Given pseudo code of Dijkstra’s Algorithm.

//Initialise single source(G,s)
While Q != 0
Do u=extract-min(Q)
S=S union {u}
For each vertex v in adj[u]
Do relax(u,v,w)
What happens when “While Q != 0” is changed to “while Q>1”?
a) While loop gets executed for v times
b) While loop gets executed for v-1 times
c) While loop gets executed only once
d) While loop does not get executed

Explanation: The while loop is executed V times in the typical execution of Dijkstra’s Algorithm. The while loop statement has been changed to only execute V – 1 times.
3. Consider the following graph.

If b is the source vertex, what is the minimum cost to reach f vertex?
a) 8
b) 9
c) 4
d) 6

Explanation: The minimum cost to reach f vertex from b vertex is 6 by having vertices g and e as intermediates.
b to g, cost is 1
g to e, cost is 4
e to f, cost is 1
hence total cost 1+4+1=6.
4. 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

Explanation: 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.
5. Dijkstra’s Algorithm is the prime example for ___________
a) Greedy algorithm
b) Branch and bound
c) Back tracking
d) Dynamic programming

Explanation: Because greedy algorithms solve problems in phases by doing what appears to be the optimal thing at each level, Dijkstra’s Algorithm is the greatest example of greedy algorithms.

6. Dijkstra’s Algorithm is used to solve _____________ problems.
a) All pair shortest path
b) Single source shortest path
c) Network flow
d) Sorting

Explanation: For single source shortest path issues, Dijkstra’s Algorithm is utilised. A single node is fixed as a source node in this approach, and the shortest paths from this node to all other nodes in the graph are identified.
7. 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

Explanation: Because the required operations in Dijkstra’s Algorithm match the specialisation of a minimum priority queue, the least priority queue is the most widely used data structure for implementing Dijkstra’s Algorithm.
8. What is the time complexity of Dijikstra’s algorithm?
a) O(N)
b) O(N3)
c) O(N2)
d) O(logN)

Explanation: Because of the use of doubly nested for loops, Dijkstra’s approach has an O(N2) time complexity. It is dependent on how the table is used.
9. 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

Explanation: Because calculating the cost to reach a destination node from a source node becomes difficult, Dijkstra’s Algorithm cannot be used to graphs with negative weight functions.

10. How many priority queue operations are involved in Dijkstra’s Algorithm?
a) 1
b) 3
c) 2
d) 4

Explanation: The number of priority queue operations involved is 3. They are insert, extract-min and decrease key.
11. How many times the insert and extract min operations are invoked per vertex?
a) 1
b) 2
c) 3
d) 0

Explanation: Because each vertex is only added to the set once and each edge in the adjacency list is only checked once during the method, the insert and extract min operations are only used once per vertex.
12. 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

Explanation: If the total number of edges in all adjacency lists is E, there will be a total of E iterations, and hence at most E decrease key operations.
13. 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)

Explanation: The time it takes to construct a binary min heap is O. (V). Each decrease key operation requires O(logV) time, and there are only E of them. As a result, the total running time is O. (ElogV).
14. The running time of Bellmann Ford algorithm is lower than that of Dijkstra’s Algorithm.
a) True
b) False

Explanation: The Bellmann Ford Algorithm has a higher number of iterations than Dijkstra’s Algorithm.

15. What is the pseudo code to compute the shortest path in Dijkstra’s algorithm?

if(T[v].Dist + C(v,w) < T[w].Dist) {
Decrease(T[w].Dist to T[v].Dist +C(v,w));
T[w].path=v; }

if(T[v].Dist + C(v,w) < T[w].Dist) {
Increase (T[w].Dist to T[v].Dist +C(v,w));
T[w].path=v; }

if(T[v].Dist + C(v,w) > T[w].Dist) {
Decrease(T[w].Dist to T[v].Dist +C(v,w);
T[w].path=v; }

if(T[v].Dist + C(v,w) < T[w].Dist) {
Increase(T[w].Dist to T[v].Dist);
T[w].path=v; }

Explanation: If the known value of the adjacent vertex(w) is not set, see if the sum of the distance from the source vertex(v) and the cost of travelling from the source to the adjacent vertex is less than the adjacent node’s existing distance. If this is the case, perform the reduce key operation.

Dijkstra’s algorithm (/dakstrz/ DYKE-strz) is a method for determining the shortest pathways between nodes in a graph, which might be used to depict road networks. Compressive strength W. Dijkstra, a computer scientist, conceived it in 1956 and published it three years later. There are numerous variations of the algorithm. The original Dijkstra algorithm discovered the shortest path between two nodes, but a more frequent form fixes a single node as the “source” node and finds shortest pathways from the source to all other nodes in the network, resulting in a shortest-path tree. The technique calculates the shortest path between a specified source node in the graph and every other node.

Leave a Reply

Your email address will not be published. Required fields are marked *