Introduction to Graph Traversal: A* and Dijkstra's Algorithms
A beginner's quiz on understanding and applying A* and Dijkstra's algorithms for graph traversal.
Questions in this quiz
15 questions on Introduction to Graph Traversal: A* and Dijkstra's Algorithms. Work through them here, then start the quiz to answer them and see your score.
1.What is the primary difference between A* and Dijkstra's algorithm?
- AA* is only used for unweighted graphs.
- BDijkstra's algorithm uses heuristics to guide its search.
- CDijkstra's algorithm cannot find the shortest path.
- DA* uses heuristics to guide its search.
2.In the context of graph traversal, what does a 'heuristic' refer to?
- AA random path selection.
- BA method to eliminate nodes.
- CA guaranteed shortest path.
- DAn estimated cost to reach the goal.
3.Which data structure is commonly used to implement Dijkstra's algorithm efficiently?
- APriority Queue
- BStack
- CQueue
- DHash Table
4.What is the time complexity of Dijkstra's algorithm using a priority queue?
- AO(E + V log V)
- BO(E^2)
- CO(V log V)
- DO(V^2)
5.In A* algorithm, what does the function f(n) = g(n) + h(n) represent?
- AThe cost from start to node n.
- BThe total cost of the path from start to goal.
- CThe cost from start to node n plus estimated cost from n to goal.
- DThe cost from node n to the goal.
6.What is a key requirement for the heuristic function in A* to guarantee finding the shortest path?
- AIt must be admissible.
- BIt must be greater than the actual cost.
- CIt must be random.
- DIt must be exact.
7.Which graph traversal algorithm is guaranteed to find the shortest path in a graph with non-negative weights?
- ABreadth-First Search
- BDijkstra's Algorithm
- CDepth-First Search
- DA* Algorithm
8.In which scenario is A* algorithm preferred over Dijkstra's algorithm?
- AWhen the graph is a tree.
- BWhen the graph has negative weights.
- CWhen the graph is unweighted.
- DWhen a heuristic can significantly reduce the search space.
9.What happens if the heuristic in A* overestimates the cost?
- AA* will run faster.
- BA* will not terminate.
- CA* may not find the shortest path.
- DA* will still find the shortest path.
10.Which of the following is true about Dijkstra's algorithm?
- AIt is faster than A* in all cases.
- BIt can handle negative weight edges.
- CIt cannot handle negative weight edges.
- DIt uses a heuristic to guide its search.
11.What is the role of the open set in A* algorithm?
- ATo store nodes that need to be evaluated.
- BTo store nodes that have been fully explored.
- CTo store the shortest path found so far.
- DTo store the heuristic values of nodes.
12.Which algorithm is more suitable for finding paths in a weighted grid with obstacles?
- ABellman-Ford Algorithm
- BA* Algorithm
- CBreadth-First Search
- DDepth-First Search
13.What is the main advantage of using a priority queue in Dijkstra's algorithm?
- AIt ensures nodes are processed in order of increasing distance.
- BIt simplifies the algorithm's implementation.
- CIt reduces memory usage.
- DIt allows for random node selection.
14.What does the closed set in A* algorithm represent?
- ANodes with the highest heuristic value.
- BNodes that have been fully evaluated.
- CNodes that are yet to be evaluated.
- DNodes that are unreachable.
15.Which algorithm can be used to find the shortest path in a graph with negative weights, but no negative cycles?
- AA* Algorithm
- BFloyd-Warshall Algorithm
- CBellman-Ford Algorithm
- DDijkstra's Algorithm