QuizzesAdvanced Graph Traversal: Mastering A* and Dijkstra's Algorithms
advanced
dsa

Advanced Graph Traversal: Mastering A* and Dijkstra's Algorithms

Test your understanding of advanced graph traversal techniques with A* and Dijkstra's algorithms.

20 minutes 10 questions Pass at 70%
Time Limit
20 minutes - timer starts when you begin
Change Answers Freely
Revisit and change any answer before submitting
Full Review After Submit
Correct answers and explanations shown for every question
Auto-submit on timeout
Quiz submits automatically when time runs out

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. 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. 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. 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. 4.Which data structure is commonly used to implement the priority queue in Dijkstra's algorithm?

    • AArray
    • BBinary heap
    • CHash table
    • DLinked list
  5. 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. 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. 7.Which property must a heuristic have for A* to guarantee finding the shortest path?

    • ACompleteness
    • BAdmissibility
    • CEfficiency
    • DConsistency
  8. 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. 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. 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.