Intermediate Graph Traversal Techniques: A* and Dijkstra's Algorithm
Explore the intricacies of A* and Dijkstra's algorithms in graph traversal.
Questions in this quiz
12 questions on Intermediate Graph Traversal Techniques: A* and Dijkstra's Algorithm. Work through them here, then start the quiz to answer them and see your score.
1.What is the primary difference between Dijkstra's Algorithm and A* Algorithm?
- ADijkstra's uses a heuristic, A* does not
- BNeither use heuristics
- CA* uses a heuristic, Dijkstra's does not
- DBoth use heuristics
2.In Dijkstra's algorithm, what data structure is commonly used to select the next node to process?
- AStack
- BQueue
- CLinked List
- DPriority Queue
3.Which of the following is true about A* algorithm's heuristic function?
- AIt can be any arbitrary function
- BIt must underestimate the true cost
- CIt must overestimate the true cost
- DIt must be linear
4.What is the time complexity of Dijkstra's algorithm using a binary heap?
- AO(V^2)
- BO(E log V)
- CO(E + V)
- DO(V log V)
5.In A* algorithm, what does the 'f(n)' function represent?
- AThe estimated total cost from start to goal through n
- BThe cost from the start node to the goal
- CThe cost from the start node to node n
- DThe heuristic cost from node n to the goal
6.Which of the following is a requirement for Dijkstra's algorithm to work correctly?
- AAll edge weights must be non-negative
- BGraph must be connected
- CGraph must be acyclic
- DGraph must be directed
7.What is the main advantage of A* over Dijkstra's algorithm?
- AA* is faster due to the heuristic
- BA* can handle negative weights
- CA* uses less memory
- DA* guarantees the shortest path
8.Which of the following is NOT a characteristic of Dijkstra's algorithm?
- AIt finds the shortest path
- BIt can handle negative weights
- CIt uses a priority queue
- DIt explores all nodes
9.In A* algorithm, if the heuristic is perfect, what is the result?
- AA* will not find the shortest path
- BA* will explore fewer nodes
- CA* will be slower than Dijkstra's
- DA* will not terminate
10.What happens if the heuristic function in A* overestimates the cost?
- AA* will be faster
- BA* will run indefinitely
- CA* may not find the shortest path
- DA* will still find the shortest path
11.Which algorithm is more suitable for finding the shortest path in a game map with obstacles?
- AA* Algorithm
- BDijkstra's Algorithm
- CDepth-First Search
- DBreadth-First Search
12.What is the role of the heuristic function in A* algorithm?
- ATo estimate the cost to the goal
- BTo determine the next node to explore
- CTo calculate the cost from the start
- DTo calculate the exact cost to the goal