2.3.1 Shortest path algorithms info
No description yet. This curated deck is ready for daily study.
Card preview (10)
What is Dijkstra’s shortest path algorithm?
An algorithm to find the shortest path between a start and end nodes on a weighted graph
what is the ‘least cost path’?
it is the best way to get from node to node
what is the purpose of Dijkstra’s algorithm?
find the shortest path from the start node to all other nodes on the graph
what is the output from Dijkstra’s algorithm?
a list which holds: - the node label - the cost of the shortest path to that node - the label of the previous node in the path
what is the A* algorithm?
An algorithm to find the shortest path between a start and end node on a weighted graph. it uses heuristics in order to speed up the process of finding a solution
what are the columns for the table for an A* algorithm?
• node • distance travelled • heuristic • distance travelled + heuristic • previous node
what is the difference between an A* algorithm and a Dijkstra’s shortest path algorithm?
• Dijkstra’s - finds the shortest path between the start node and all other nodes • A* - uses heuristics, only finds the shortest path between the start and end node
what is a heuristic/heuristic function?
• a function which provides an estimate of the minimum distance/weight between a given node and the target node
what are the advantages and disadvantages of Dijkstra’s algorithm?
• will always find the shortest path between the start and end node • the algorithm can be inefficient as it evaluates routes that are unecessary
what are the advantages and disadvantages of the A* algorithm?
• more efficient so can make better choices about the next path to take • requires a good heuristic function