SW19: Shortest Paths (Dijkstra's Algorithm)

Question 1

Fill in the Blanks: Dijkstra’s algorithm builds a _____ Tree.

Answer 1

Shortest Path

Question 2

Dijkstra’s Algorithm follows which algorithm design paradigm?
A. Divide and Conquer
B. Greedy Method
C. Backtracking
D. Dynamic Programming

Answer 2

B. Greedy Method

Question 3

What is the standard time complexity of Dijkstra’s algorithm using a Min-Heap (Priority Queue)?
A. O(V + E)
B. O(E log V)
C. O(V²)
D. O(log V)

Answer 3

B. O(E log V)

Question 4

Fill in the Blanks: _____ is the step where d[v]is improved using d[u].

Answer 4

Relaxation

Question 5

Fill in the Blanks: _____ is weight < 0 that causes standard Dijkstra to fail.

Answer 5

Negative Edge

Question 6

Fill in the Blanks: _____ is the efficient greedy algorithm for non-negative weights Dijkstra’s Algorithm

Answer 6

Dijkstra’s Algorithm

Question 7

Fill in the Blanks: _____ is the data structure optimizing the “extract-min” operation Priority Queue

Answer 7

Priority Queue

Question 8

Fill in the Blanks: _____ is the algorithm that handles negative weights (but not negative cycles) Bellman-Ford Algorithm

Answer 8

Bellman-Ford Algorithm

Question 9

True or False: Dijkstra’s algorithm can be used to find the shortest path from all sources to all destinations simultaneously.

Answer 9

TRUE

Question 10

Fill in the Blanks: In Dijkstra’s algorithm, the operation of updating the distance of a neighbor is called _____.

Answer 10

Relaxation

Question 11

What happens if we run Dijkstra’s algorithm on a graph with a negative cycle?
A. It will detect and remove the cycle
B. It automatically switches to Bellman-Ford
C. It will still produce correct shortest paths
D. It may enter an infinite loop or give incorrect results

Answer 11

D. It may enter an infinite loop or give incorrect results

Question 12

Fill in the Blanks: The initial distance to the source vertex in Dijkstra’s algorithm is set to _____.

Answer 12

FALSE

Question 13

If we use a simple array instead of a heap for Dijkstra’s, the time complexity becomes:
A. O(V²)
B. O(V log V)
C. O(E log V)
D. O(E + V)

Answer 13

A. O(V²)

Question 14

Dijkstra’s algorithm fails if the graph contains:
A. Zero-weight edges
B. Positive cycles
C. Negative-weight edges
D. Disconnected components

Answer 14

C. Negative-weight edges

Question 15

Fill in the Blanks: The process of picking the vertex with the smallest distance is an example of a _____ choice.

Answer 15

greedy

Question 16

True or False: Dijkstra’s algorithm works on both directed and undirected graphs.

Answer 16

TRUE

Question 17

Which data structure is most efficient for finding the vertex with the minimum tentative distance in Dijkstra’s?
A. Stack
B. Queue
C. Priority Queue (Min-Heap)
D. Linked List

Answer 17

C. Priority Queue (Min-Heap)

Question 18

True or False: Dijkstra’s algorithm can be used to find the shortest path from all sources to all destinations simultaneously.

Answer 18

FALSE

Question 19

Fill in the Blanks: The initial distance to all other vertices (except source) is set to _____.

Answer 19

infinity

Question 20

If d[u] = 10, weight(u, v) = 5 and d[v] = 20, what will be the new value of d[v] after relaxation?
A. 25
B. 10
C. 5
D. 15

Answer 20

D. 15