Shortest path algorithms (Dijkstra’s, Bellman-Ford) MCQs

33
Score: 0
Attempted: 0/33

1. What is the primary purpose of Dijkstra’s algorithm?
(A) To find the shortest path in an unweighted graph
(B) To find the shortest path in a weighted graph
(C) To find all paths in a graph
(D) To find the longest path in a graph

2. Which data structure is typically used in Dijkstra’s algorithm to store the next vertex to process?
(A) Stack
(B) Queue
(C) Priority queue
(D) Array

3. What is the time complexity of Dijkstra’s algorithm using a priority queue implemented with a binary heap?
(A) O(V²)
(B) O(E + V log V)
(C) O(V log V)
(D) O(E log V)

4. What is the primary disadvantage of Dijkstra’s algorithm?
(A) It cannot handle negative weight edges
(B) It is too slow for large graphs
(C) It is too complex to implement
(D) It cannot find the shortest path

5. Which algorithm can handle graphs with negative weight edges?
(A) Dijkstra’s algorithm
(B) Bellman-Ford algorithm
(C) Both algorithms
(D) Neither algorithm

6. What is the time complexity of the Bellman-Ford algorithm?
(A) O(E)
(B) O(V + E)
(C) O(VE)
(D) O(V²)

7. What does the Bellman-Ford algorithm detect in a graph?
(A) Shortest paths only
(B) Negative weight cycles
(C) All paths
(D) Minimum spanning tree

8. Which algorithm is generally faster for dense graphs?
(A) Dijkstra’s algorithm
(B) Bellman-Ford algorithm
(C) Both are equally fast
(D) Neither is efficient for dense graphs

9. Which algorithm initializes distances from the source to all other vertices to infinity?
(A) Dijkstra’s algorithm
(B) Bellman-Ford algorithm
(C) Both algorithms
(D) Neither algorithm

10. In Dijkstra’s algorithm, how is the next vertex selected?
(A) The vertex with the maximum distance
(B) The vertex with the minimum distance
(C) The vertex with the most edges
(D) The vertex with the least connections

11. What is the key step in the Bellman-Ford algorithm?
(A) Updating the shortest path estimates for all vertices
(B) Selecting the vertex with the least edges
(C) Using a priority queue to manage vertices
(D) Ignoring negative weight edges

12. What happens if a negative weight cycle exists in the graph?
(A) Dijkstra’s algorithm will fail
(B) Bellman-Ford will give incorrect results
(C) Both algorithms will give correct results
(D) Both algorithms will fail

13. Which of the following statements is true about Dijkstra’s algorithm?
(A) It can be used on directed graphs only
(B) It guarantees the shortest path for all edges
(C) It works well with negative weight edges
(D) It is not suitable for large graphs

14. What is a primary use case for the Bellman-Ford algorithm?
(A) Finding the minimum spanning tree
(B) Finding shortest paths in graphs with negative weights
(C) Finding the longest path
(D) Performing depth-first search

15. Which algorithm requires fewer iterations when the graph has fewer edges?
(A) Dijkstra’s algorithm
(B) Bellman-Ford algorithm
(C) Both have the same number of iterations
(D) Neither algorithm is affected by edges

16. What does the relaxation step in both algorithms involve?
(A) Updating the weight of edges
(B) Reducing the distance to a vertex
(C) Checking for cycles
(D) Adding new edges to the graph

17. Which algorithm can be implemented with a simple array to store distances?
(A) Dijkstra’s algorithm
(B) Bellman-Ford algorithm
(C) Both algorithms
(D) Neither algorithm

18. In which scenario would you prefer Dijkstra’s algorithm over Bellman-Ford?
(A) When the graph has negative weights
(B) When the graph is dense
(C) When you need a simpler implementation
(D) When performance is critical in a non-negative weighted graph

19. Which algorithm will give you the shortest path tree rooted at the source?
(A) Dijkstra’s algorithm
(B) Bellman-Ford algorithm
(C) Both algorithms
(D) Neither algorithm

20. What is the key assumption of Dijkstra’s algorithm regarding edge weights?
(A) All edges must have the same weight
(B) Edge weights must be non-negative
(C) Edge weights can be negative
(D) Edge weights must be integers

21. How many times does the Bellman-Ford algorithm need to relax edges?
(A) V times
(B) E times
(C) V-1 times
(D) E-1 times

22. What can be concluded if the distance to a vertex in Dijkstra’s algorithm does not change?
(A) The vertex is unreachable
(B) The vertex has no neighbors
(C) The shortest path has been found
(D) The algorithm is incorrect

23. Which algorithm can handle directed graphs?
(A) Dijkstra’s algorithm
(B) Bellman-Ford algorithm
(C) Both algorithms
(D) Neither algorithm

24. Which algorithm would be best for a network with varying costs for different paths?
(A) Dijkstra’s algorithm
(B) Bellman-Ford algorithm
(C) Both algorithms are suitable
(D) Neither algorithm is suitable

25. In Bellman-Ford, what is done if a distance can still be reduced after V-1 iterations?
(A) The algorithm terminates
(B) A negative weight cycle exists
(C) The algorithm continues indefinitely
(D) The algorithm returns incorrect results

26. How does the initialization of distances differ between the two algorithms?
(A) Both start from the same vertex
(B) Dijkstra initializes to infinity; Bellman-Ford initializes to zero
(C) Dijkstra initializes to zero; Bellman-Ford initializes to infinity
(D) Both initialize distances to zero

27. Which algorithm uses the principle of greedy approach?
(A) Dijkstra’s algorithm
(B) Bellman-Ford algorithm
(C) Both algorithms
(D) Neither algorithm

28. Which of the following is an example of an application for Dijkstra’s algorithm?
(A) Finding the fastest route in GPS navigation
(B) Finding the minimum spanning tree
(C) Detecting cycles in a graph
(D) Sorting a list of numbers

29. Which of the following is an example of an application for the Bellman-Ford algorithm?
(A) Finding the fastest route in GPS navigation
(B) Network routing with negative weights
(C) Finding the minimum spanning tree
(D) Sorting a list of numbers

30. In a directed graph, can Dijkstra’s algorithm yield different paths from the same source to the same destination?
(A) Yes, depending on the implementation
(B) No, it always gives the same path
(C) Yes, but only with negative weights
(D) No, it always gives the longest path

31. What type of graph can the Bellman-Ford algorithm be applied to?
(A) Only undirected graphs
(B) Only directed graphs
(C) Both directed and undirected graphs with negative weights
(D) Only graphs without cycles

32. Which of the following can improve the performance of Dijkstra’s algorithm?
(A) Using an unordered list
(B) Using a Fibonacci heap
(C) Ignoring negative weights
(D) Reducing the number of vertices

33. What happens if Dijkstra’s algorithm encounters a negative edge?
(A) It continues processing normally
(B) It terminates with an error
(C) It yields incorrect results
(D) It only processes positive edges

Data Structures MCQs

Basic Concepts

Linear Data Structures MCQs

Non-Linear Data Structures MCQs

Hashing MCQs MCQs

Hash Tables

Sorting and Searching Algorithms MCQs

Miscellaneous

Shortest path algorithms (Dijkstra’s, Bellman-Ford) MCQs
By: Prof. Dr. Fazal Rehman | Last updated: May 15, 2025

Related Posts: