Path Finding Algorithms

Question 1

Dijkstra’s Algorithm

Answer 1

Dijkstra’s Algorithm: Finds shortest path between 2 nodes in weighted graph
- Implemented using priority queue, w/ smallest distances being stored at front of list

Question 2

A* Algorithm

Answer 2

A* Algorithm: General path-finding algorithm, has 2 cost functions:
1) First cost function, actual cost between 2 nodes (same cost as in Dijkstra’s algorithm)
2) Second cost function, approximate cost from node x to final node (called heuristic), aims to make shortest path finding process more efficient
- Approximate cost might be estimate of length between x & final node, calculated using trigonometry
- When calculating the distance between 2 nodes, approximate cost is added onto actual cost
- Used to determine which node is visited next
- Differs from Dijkstra’s algorithm, as a node w/ a lower actua cost may be rejected in favour of node w/ lower total cost
- Meant to reduce total time taken to find shortest path