2.3.5 Path Finding Algorithms

• 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 the process of using Dijkstra’s algorithm to find the shortest path?

  1. Start from the root node.
  2. Add distances to neighbouring nodes to the priority queue.
  3. Remove the node with the smallest distance.
  4. Update distances for connected nodes.
  5. Repeat until the goal node is reached.
• What is the initial distance for nodes that cannot be reached in Dijkstra’s algorithm?

  ∞ (infinity)
• What should be filled in the 'Node' column when using Dijkstra’s algorithm?

  Nodes connected to the root node
• What happens when the total distance through a removed node is smaller?

  Update the distance to the smaller value
• What are the two cost functions in the A* algorithm?

  Actual cost and approximate cost
• What is a heuristic in the context of the A* algorithm?

  An approximate cost to the final node
• How is the total cost calculated in the A* algorithm?

  Add the approximate cost to the actual cost
• What happens if a node with a lower actual cost is rejected in A* algorithm?

  It may be due to a lower total cost
• What is the process of using the A* algorithm to find the shortest distance?

  1. Add a heuristic column to the table.
  2. Calculate total cost by adding heuristic to actual cost.
  3. Select the route with the lowest total cost.
  4. Repeat until the shortest route is found.
• What does the effectiveness of the A* algorithm depend on?

  The accuracy of the heuristics used