2.3.5 - Pathfinding Algorithms Flashcards
1
Q
What is the purpose of a pathfinding algorithm?
A
To find the shortest path between two nodes in a weighted graph.
2
Q
What are the two types of pathfinding algorithm?
A
Dijkstra’s Algorithm.
The A* Algorithm.
3
Q
What can graphs be used to symbolise?
A
Towns and cities and the distances between the two.
Networks with nodes representing devices and arc costs representing network traffic.
4
Q
What data structure is Dijkstra’s algorithm implemented using?
A
A priority queue.
5
Q
How does Dijkstra’s algorithm differ from the A* algorithm?
A
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.
