GCSE Link: None

Dijkstra's Shortest Path Algorithm is an optimisation algorithm which finds the shortest path between a start node and any other node of a weighted graph.

This is how it works:

  1. Firstly, create a distances dictionary which will store the shortest distance from the start node to every other node. At the beginning, every value is set to infinity (because the other nodes haven't been discovered yet) except the start node, which is set to 0.
  2. Next, create a previous nodes dictionary which will store the previous node from each of the nodes (e.g. if the shortest path from A to G is ADG, then prev['G'] will be 'D' and prev['D'] will be 'A'). Initialise all values here to null, because we haven't discovered any paths yet.
  3. Then, create a list of nodes to visit. Add every node in the graph to that list.
  4. Find the node in the list with the lowest distance value. (The first time round, this will be the start node.) We'll call this node v.
  5. Now, repeat steps 6 and 7 with every neighbour of v which is still in the list of nodes to visit. We'll call the neighbouring node u.
  6.     Calculate the new distance value of u: the distance of v plus the weight of the edge between v and u.
  7.     If this new distance is less than the distance of u, update the distance of u to be the new distance and set prev[u] to v.
  8. Remove v from the list of nodes to visit. If the list is not empty, go back to step 4.
  9. Otherwise, the algorithm is finished.

Diagram 1 shows a step-by-step animation of Dijkstra's Shortest Path Algorithm Use the arrows to navigate.

Diagram 1


Can you think of a real-world application of Dijkstra's Shortest Path Algorithm?

For example: finding the shortest routes between two locations in Google Maps (where edges represent roads and the weights show the travel time); network routing (nodes represent routers and weights show the latency); etc.