2.3.5 - Pathfinding Algorithms

Question 1

What is the purpose of a pathfinding algorithm?

Answer 1

To find the shortest path between two nodes in a weighted graph.

Question 2

What are the two types of pathfinding algorithm?

Answer 2

Dijkstra’s Algorithm.

The A* Algorithm.

Question 3

What can graphs be used to symbolise?

Answer 3

Towns and cities and the distances between the two.

Networks with nodes representing devices and arc costs representing network traffic.

Question 4

What data structure is Dijkstra’s algorithm implemented using?

Answer 4

A priority queue.

Question 5

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

Answer 5

The A* algorithm uses heuristics to find an approximate value. This means that every path doesn’t have to be checked and so the algorithm is much faster and only slightly less effective.