2. 3. 5 Path Finding Algorithms

Question 1

Dijkstra’s shortest path algorithm

Answer 1

• Finds shortest path between two nodes in a weighted graph
• Graphs used as abstraction for real life scenarios, nodes and edges can represent different entities
• Graphs can be used to model networks; nodes represent devices and costs/weighting may represent network traffic
• Algorithm in this sort of scenario would be used to determine the optimal route to use when forwarding packets thorough a network
• Regardless of scenario, the algorithm used to work out shortest path using a consistent method each time, algorithm commonly implemented using a priority queue
• Smallest distances would be stored at the front of the queue

Question 2

How it works

Answer 2

• Let distance of start vertex from start vertex = 0
• Let distance of all other vertices from start = ∞ (infinity)
• Repeat
• Visit the unvisited vertex with the smallest known distance from the start vertex
• For the current vertex, examine its unvisited neighbours
• For the current vertex, calculate distance of each neighbour from start vertex
• If the calculated distance of a vertex is less than the known distance, update the shortest distance
• Update the previous vertex for each of the updated distances
• Add the current vertex to the list of visited vertices
• Until all vertices visited

Question 3

Examples of Dijkstra’s shortest path algorithm

Answer 3

View the Word doc

Question 4

A* algorithm

Answer 4

• General path-finding algorithm, improvement of Dijkstra’s algorithm, has two cost functions
• The actual cost between nodes, the same cost as measured in Dijkstra’s algorithm
• An approximate cost from node x to the final node, this is called a heuristic, aims to make shortest path finding process more efficient
• Approximate cost might be an estimate between x and final node, it is calculated using trigonometry
• When calculating distance between nodes in this algorithm, approximate cost is added to the actual cost, used to determine which node is visited next
• Node with lower actual cost may be rejected in favour with a lower total cost, this differs from Dijkstra’s algorithm
• This is meant to reduce total time taken to find the shortest path

Question 5

Steps

Answer 5

• Initialise open and closed lists
• Make the start vertex current
• Calculate heuristic distance of start vertex to destination (h)
• Calculate f value for start vertex (f = g + h, where g = 0)
• WHILE current vertex is not the destination
• FOR each vertex adjacent to current
• IF vertex not in closed list and not in open list THEN
• Add vertex to open list
• Calculate distance from start (g)
• Calculate heuristic distance to destination (h)
• Calculate f value (f = g + h)
• IF new f value < existing f value or there is no existing f value THEN
• Update f value
• Set parent to be the current vertex
• END IF
• END IF
• NEXT adjacent vertex
• Add current vertex to closed list
• Remove vertex with lowest f value from open list and make it current
• END WHILE

Question 6

Example

Answer 6

View the Word doc

Question 7

Strengths and weaknesses

Answer 7

• Only gives back what we requested rather than every possible route
• Speed depends on chance
• Relies on good heuristic distance