Shortest Path Algorithms

Djikstra’s Shortest Path Algorithm

There are a number of shortest path algorithms, but one of the most famous is Djikstra’s. In this algorithm, a weighted graph is traversed to discover the distance between all nodes.

When running Djikstra’s algorithm, it is useful to make use of a trace table to identify each of the shortest paths and also a list which identifies which nodes have been visited. Aside from the first node, initially all distances are set as infinite as they have not yet been tested.

Djikstra example 1

Once the starting node has been chosen, each path is tested to find the shortest paths between all nodes. In the example below, the shortest path from A to the next node is tested, then recorded in the table. The infinite distance from A is now overwritten as the value of 2 is lower than infinity, and the node (referred to as a vertex in a graph) before C is recorded in the table.

Djikstra example 2

This process continues until all paths have been tested and the shortest distance from A to that node has been recorded.

Finally, the table is used to trace the shortest path backward from the end node to form a shortest path.

Djikstra example final

The A* Algorithm

The A* algorithm is studied within the OCR A Level specification, but is a useful pathfinding algorithm to be aware of for all students as it shows how Dijkstra’s Algorithm can be made more efficient. Rather than searching the paths between all nodes within a graph, the A* algorithm performs a directional search, seeking a path between two nodes.

When looking at the A* algorithm we start with an educated guess of the distance between two nodes. This figure is not simply plucked from the air (remember that heuristics means ‘close enough’), but uses a best case calculation.

When using a grid, we can start by assuming one move in a straight line within a grid is 1 space:

A star Algorithm single move

Using Pythagoras Theorum, we can then calculate that a diagonal move is 1.4:

A star Algorithm diagonal

This movement ‘cost’ is referred to as g in the algorithm and holds the value that has already been travelled from the starting node. Using these calculations, we can then identify which node to follow for the A* algorithm between two nodes.

To calculate the next node to follow from A, all available surrounding nodes are given a g value (shown below in the top left corners):

A star Algorithm calculating g

After this, a heuristic value is added which is referred to as h. In the example below, there is no obstacle in the way, so we can calculate the heuristic value ‘as the crow flies’:

A star Algorithm - calculating h

This is repeated for all surrounding nodes and the two values are added together to create the f value. One this has been completed, the smallest value is selected as the node to follow:

A star Algorithm - calculating f

Next, the same process is applied to the new node, calculating the distance travelled (g), the heuristic distance left (h) and adding together to form the total distance (f).

A star Algorithm - following a path

Finally, the same process is applied until the goal node has been reached and there are no further clear alternatives to follow.

A star Algorithm - Final Node

Log in with your A Level student or teacher account for an extended tutorial on dealing with objects within the A* algorithm.

Question

Answer

  • Calculate the shortest path using the A* Algorithm for the following map:

    A star question 1

  • In this case, the 3.8 route is followed consistently as no other smaller f cost is calculated.

    A star answer f

Looking for More?

Sign in with your A Level Account to access the following extras on this page for members:

Scribbl.it Notes

Exam Practice

A Level Content

Looking for something else? Check back soon as new resources are added every week!

Not a member yet? Sign Up or Log In below