2.3.1 Shortest path algorithms info

Question 1

What is Dijkstra’s shortest path algorithm?

Answer 1

An algorithm to find the shortest path between a start and end nodes on a weighted graph

Question 2

what is the ‘least cost path’?

Answer 2

it is the best way to get from node to node

Question 3

what is the purpose of Dijkstra’s algorithm?

Answer 3

find the shortest path from the start node to all other nodes on the graph

Question 4

what is the output from Dijkstra’s algorithm?

Answer 4

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

Question 5

what is the A* algorithm?

Answer 5

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

Question 6

what are the columns for the table for an A* algorithm?

Answer 6

• node
• distance travelled
• heuristic
• distance travelled + heuristic
• previous node

Question 7

what is the difference between an A* algorithm and a Dijkstra’s shortest path algorithm?

Answer 7

• 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

Question 8

what is a heuristic/heuristic function?

Answer 8

• a function which provides an estimate of the minimum distance/weight between a given node and the target node

Question 9

what are the advantages and disadvantages of Dijkstra’s algorithm?

Answer 9

• will always find the shortest path between the start and end node
• the algorithm can be inefficient as it evaluates routes that are unecessary

Question 10

what are the advantages and disadvantages of the A* algorithm?

Answer 10

• more efficient so can make better choices about the next path to take
• requires a good heuristic function