2.3.5 Path FInding Algorithms
No description yet. This curated deck is ready for daily study.
Card preview (7)
What is Dijkstra’s algorithm?
A shortest path algorithm used to find the shortest distance between two nodes on a weighted graph
Outline the stages of Dijkstra’s algorithm.
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
What is the A* algorithm?
A general path-finding algorithm that uses heuristics to approximate the shortest path between two nodes on a weighted graph
Outline the stages of the A* algorithm.
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
How does the A* algorithm differ from Dijkstra’s algorithm?
A* algorithm has two cost functions: Actual cost Approximate cost
Why are heuristics used in the A* algorithm?
To calculate an approximate cost from the starting node to the final node Aims to make finding path more efficient
State a disadvantage of using the A* algorithm.
The speed of the algorithm is constrained by the accuracy of the heuristic methods