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
Answer: B) To find the shortest path in a weighted graph
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
Answer: C) Priority queue
What is the time complexity of Dijkstra’s algorithm using a priority queue implemented with a binary heap?
A) O(V^2)
B) O(E + V log V)
C) O(V log V)
D) O(E log V)
Answer: B) O(E + V log V)
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
Answer: A) It cannot handle negative weight edges
Which algorithm can handle graphs with negative weight edges?
A) Dijkstra’s algorithm
B) Bellman-Ford algorithm
C) Both algorithms
D) Neither algorithm
Answer: B) Bellman-Ford algorithm
What is the time complexity of the Bellman-Ford algorithm?
A) O(E)
B) O(V + E)
C) O(VE)
D) O(V^2)
Answer: C) O(VE)
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
Answer: B) Negative weight cycles
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
Answer: A) Dijkstra’s algorithm
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
Answer: C) Both algorithms
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
Answer: B) The vertex with the minimum distance
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
Answer: A) Updating the shortest path estimates for all vertices
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
Answer: B) Bellman-Ford will give incorrect results
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
Answer: B) It guarantees the shortest path for all edges
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
Answer: B) Finding shortest paths in graphs with negative weights
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
Answer: A) Dijkstra’s algorithm
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
Answer: B) Reducing the distance to a vertex
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
Answer: B) Bellman-Ford algorithm
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
Answer: D) When performance is critical in a non-negative weighted graph
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
Answer: A) Dijkstra’s algorithm
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
Answer: B) Edge weights must be non-negative
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
Answer: C) V-1 times
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
Answer: C) The shortest path has been found
Which algorithm can handle directed graphs?
A) Dijkstra’s algorithm
B) Bellman-Ford algorithm
C) Both algorithms
D) Neither algorithm
Answer: C) Both algorithms
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
Answer: A) Dijkstra’s algorithm
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
Answer: B) A negative weight cycle exists
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
Answer: C) Dijkstra initializes to zero; Bellman-Ford initializes to infinity
Which algorithm uses the principle of greedy approach?
A) Dijkstra’s algorithm
B) Bellman-Ford algorithm
C) Both algorithms
D) Neither algorithm
Answer: A) Dijkstra’s algorithm
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
Answer: A) Finding the fastest route in GPS navigation
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
Answer: B) Network routing with negative weights
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
Answer: A) Yes, depending on the implementation
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
Answer: C) Both directed and undirected graphs with negative weights
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
Answer: B) Using a Fibonacci heap
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
Answer: C) It yields incorrect results
Basic Concepts
Non-Linear Data Structures MCQs
Sorting and Searching Algorithms MCQs
- Data Structures MCQs 1
- Data Structures MCQs 2
- Data Structures MCQs 3
- Data Structures MCQs 4
- Data Structures MCQs 5
- Stacks Solved MCQs
- Queues MCQs
- pointer mcqs
- Array MCQs