2.3.1 Path finding algorithms

Question 1

Explain Dijkstra’s algorithm

Answer 1

• Path finding alg
• Shortest path between two nodes
• You know how to do this from FM

Question 2

Explain A star algorithm

Answer 2

• Improvement on Dijkstra’s
• Two cost functions
• Cost between two nodes and approximate cost from node x to the final node called a heuristic

Question 3

What are the advantages and disadvantages of A star

Answer 3

• If good heuristics are used the shortest path can be found much quicker
• Better heuristics take longer to calculate