Q. In the context of Dijkstra's algorithm, what does 'relaxation' mean?
A.
Updating the distance to a node if a shorter path is found
B.
Removing nodes from the graph
C.
Adding new edges to the graph
D.
Resetting the algorithm
Show solution
Solution
Relaxation refers to the process of updating the shortest known distance to a node if a shorter path is found through another node.
Correct Answer:
A
— Updating the distance to a node if a shorter path is found
Learn More →
Q. What condition must be met for Dijkstra's algorithm to work correctly?
A.
All edge weights must be positive
B.
The graph must be a tree
C.
All nodes must be connected
D.
The graph must be directed
Show solution
Solution
Dijkstra's algorithm requires that all edge weights be non-negative to ensure that the shortest path is correctly identified.
Correct Answer:
A
— All edge weights must be positive
Learn More →
Q. What is the main difference between Dijkstra's algorithm and the Bellman-Ford algorithm?
A.
Dijkstra's algorithm is faster for all graphs
B.
Bellman-Ford can handle negative weights, Dijkstra's cannot
C.
Dijkstra's algorithm is only for directed graphs
D.
Bellman-Ford is more complex to implement
Show solution
Solution
The main difference is that the Bellman-Ford algorithm can handle graphs with negative weight edges, while Dijkstra's algorithm cannot.
Correct Answer:
B
— Bellman-Ford can handle negative weights, Dijkstra's cannot
Learn More →
Q. What is the time complexity of Dijkstra's algorithm using a binary heap?
A.
O(V^2)
B.
O(E log V)
C.
O(V log V)
D.
O(E + V)
Show solution
Solution
The time complexity of Dijkstra's algorithm using a binary heap is O(E log V), where E is the number of edges and V is the number of vertices.
Correct Answer:
B
— O(E log V)
Learn More →
Q. What type of graph representation is most efficient for Dijkstra's algorithm?
A.
Adjacency matrix
B.
Adjacency list
C.
Edge list
D.
Incidence matrix
Show solution
Solution
An adjacency list is generally more efficient for Dijkstra's algorithm, especially for sparse graphs, as it allows for quicker access to neighboring nodes.
Correct Answer:
B
— Adjacency list
Learn More →
Q. Which of the following is a limitation of Dijkstra's algorithm?
A.
It cannot handle negative weight edges
B.
It is not efficient for dense graphs
C.
It cannot find paths in directed graphs
D.
It requires a complete graph
Show solution
Solution
Dijkstra's algorithm cannot handle graphs with negative weight edges, as it may lead to incorrect results.
Correct Answer:
A
— It cannot handle negative weight edges
Learn More →
Showing 1 to 6 of 6 (1 Pages)
