Advanced Graph Traversal: Mastering A* and Dijkstra's Algorithms
Test your understanding of advanced graph traversal techniques with A* and Dijkstra's algorithms.
Questions in this quiz
10 questions on Advanced Graph Traversal: Mastering A* and Dijkstra's Algorithms. Work through them here, then start the quiz to answer them and see your score.
1.Which of the following is a key difference between A* and Dijkstra's algorithm?
- AA* can only be used on weighted graphs, while Dijkstra's can be used on unweighted graphs.
- BDijkstra's algorithm guarantees the shortest path, while A* does not.
- CA* uses a heuristic to guide its search, while Dijkstra's does not.
- DDijkstra's algorithm is faster than A* in all cases.
2.In the context of A* algorithm, what is the role of the heuristic function?
- AIt calculates the exact cost from the start node to the current node.
- BIt estimates the cost from the current node to the goal.
- CIt checks for cycles in the graph.
- DIt determines the total cost of the path from start to goal.
3.Why is Dijkstra's algorithm considered optimal for finding the shortest path?
- AIt only works on unweighted graphs.
- BIt relies on a heuristic to guide the search.
- CIt uses a priority queue to always expand the least costly node.
- DIt explores all possible paths.
4.Which data structure is commonly used to implement the priority queue in Dijkstra's algorithm?
- AArray
- BBinary heap
- CHash table
- DLinked list
5.What is the time complexity of Dijkstra's algorithm when implemented with a binary heap?
- AO(V + E log V)
- BO(E log V)
- CO(V log V + E)
- DO(V^2)
6.In A* algorithm, what happens if the heuristic function overestimates the cost to reach the goal?
- AThe algorithm will ignore the heuristic.
- BThe algorithm will terminate immediately.
- CThe algorithm will run faster.
- DThe algorithm may not find the shortest path.
7.Which property must a heuristic have for A* to guarantee finding the shortest path?
- ACompleteness
- BAdmissibility
- CEfficiency
- DConsistency
8.What is the primary advantage of using A* over Dijkstra's algorithm?
- AA* is easier to implement.
- BA* is generally faster due to its heuristic guidance.
- CA* requires less memory.
- DA* can handle negative weights.
9.How does Dijkstra's algorithm handle graphs with negative edge weights?
- AIt cannot handle negative weights.
- BIt will find the longest path instead.
- CIt requires a modified version to handle negative weights.
- DIt works correctly with negative weights.
10.What is the effect of using a non-admissible heuristic in A* algorithm?
- AThe algorithm will ignore the heuristic.
- BThe algorithm will not terminate.
- CThe algorithm may not find the shortest path.
- DThe algorithm will run in exponential time.