Dijkstra’s Algorithm and A*

• What does Dijkstra’s algorithm find in a weighted graph?

  The shortest path between two nodes
• How can graphs be used in real life?

  To model networks and represent entities
• In a network scenario, what does Dijkstra’s algorithm determine?

  The optimal route for forwarding packets
• What data structure is commonly used to implement Dijkstra’s algorithm?

  A priority queue
• What is stored at the front of the priority queue in Dijkstra’s algorithm?

  The smallest distances
• What is the first step in using Dijkstra’s algorithm?

  • Start from the root node (A)
  • Add distances to neighbouring nodes (B, C, D)
  • Mark unreachable nodes with ∞
• What should you fill in the ‘Node’ column when demonstrating Dijkstra’s algorithm?

  Nodes connected to the root node
• What does the ‘Total distance’ column represent in Dijkstra’s algorithm?

  The sum of distances from the root node
• Why is it important to keep track of visited nodes in Dijkstra’s algorithm?

  To avoid going back on the path already taken
• What happens in Step 2 of Dijkstra’s algorithm?

  • Remove the first node from the queue
  • Traverse connected nodes without backtracking
  • Update distances if a shorter path is found
• What is the significance of the priority queue in Dijkstra’s algorithm?

  It orders nodes by their distance from the root
• How does Dijkstra’s algorithm update the cost associated with a node?

  By comparing new paths to existing costs
• What is the final step in Dijkstra’s algorithm?

  • Confirm the shortest path by tracing back
  • The shortest path found is ADE
  • The total cost is 11
• What is the first cost function in the A* algorithm?

  The actual cost between two nodes
• What is the purpose of the heuristic in the A* algorithm?

  To make the shortest path finding more efficient
• How is the total cost calculated in the A* algorithm?

  By adding the approximate cost to the actual cost
• What is the difference in node selection between Dijkstra’s and A* algorithms?

  • Dijkstra’s selects nodes with lower actual cost
  • A* selects nodes with lower total cost
  • A* aims to reduce total time taken
• What is required when using the A* algorithm compared to Dijkstra’s algorithm?

  • An extra column for heuristic costs
  • The same method as Dijkstra’s algorithm
  • Selection of the lowest total cost route
• How do heuristics affect the A* algorithm's efficiency?

  They allow quicker path finding
• What is the relationship between the heuristic and the actual cost in the A* algorithm?

  The heuristic is added to the actual cost