Dijkstra Short Path Algorithm Interactive Task

Every time you use a sat nav, plan a journey on a map app, or search for the fastest route across a transport network, you are using ideas from graph theory. A road map can be represented as a graph: towns, junctions or stations are nodes, and the roads, railways or paths between them are edges. If each edge has a value, such as distance, time or cost, we can use an algorithm to find the shortest route.

One of the most famous algorithms for solving this problem is Dijkstra’s Shortest Path Algorithm. It was created in 1956 by Dutch computer scientist Edsger W. Dijkstra. The story goes that Dijkstra came up with the algorithm while sitting in a café in Amsterdam, trying to find an elegant way to calculate the shortest route between two cities. He later said that he designed it in about twenty minutes, without even using pencil and paper!

The algorithm works by starting at one node and gradually building up the shortest known distance to every other node in the graph. At each step, it chooses the unvisited node with the smallest temporary distance, marks it as visited, and updates the distances to its neighbouring nodes. By repeating this process, the algorithm eventually finds the shortest path from the starting node to the destination.

Dijkstra’s Algorithm is still important today. It has influenced route-planning systems, network routing, robotics, logistics, games, and many other areas of computer science. It is also a great example of how a problem can be solved by breaking it down into clear, repeatable steps.

In this interactive activity, you will practise applying Dijkstra’s Algorithm to a range of different weighted directed graphs. For each challenge, study the graph carefully, complete the table step by step, and identify the shortest path and total distance from the starting node to the target node. Use the check button to test your answers and improve your understanding of how the algorithm works.