QuizzesIntroduction to Graph Traversal: A* and Dijkstra's Algorithms
beginner
dsa

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.

15 minutes 15 questions Pass at 70%
Time Limit
15 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

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. 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. 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. 3.Which data structure is commonly used to implement Dijkstra's algorithm efficiently?

    • APriority Queue
    • BStack
    • CQueue
    • DHash Table
  4. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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