2.3.5 Path FInding Algorithms

Question 1

What is Dijkstra’s algorithm?

Answer 1

A shortest path algorithm used to find the shortest distance between two nodes on a weighted graph

Question 2

Outline the stages of Dijkstra’s algorithm.

Answer 2

Priority queue created from starting node
Distances added (0 to starting node, ∞ to others)
Remove front node and add to visited list
Update distances of each node connected to visited node
Sort priority queue
Repeats until all visited

Question 3

What is the A* algorithm?

Answer 3

A general path-finding algorithm that uses heuristics to approximate the shortest path between two nodes on a weighted graph

Question 4

Outline the stages of the A* algorithm.

Answer 4

Priority queue created from starting node
Distances from starting node, heuristic distances to end node and sum
Remove front node and add to visited list
Update all data for nodes connected to visited nodes
Sort priority queue
Repeats until all visited

Question 5

How does the A* algorithm differ from Dijkstra’s algorithm?

Answer 5

A* algorithm has two cost functions:
Actual cost
Approximate cost

Question 6

Why are heuristics used in the A* algorithm?

Answer 6

To calculate an approximate cost from the starting node to the final node
Aims to make finding path more efficient

Question 7

State a disadvantage of using the A* algorithm.

Answer 7

The speed of the algorithm is constrained by the accuracy of the heuristic methods