How to Use Dijkstra's Algorithm

If there’s one thing us students love it’s sleep. But when class starts at 9, we have to sacrifice our precious sleep so we can get up early enough to have time to walk to school. If we want the maximum time in our nice, warm beds, then we’ll have to make sure we’re walking the quickest way to school but when there are lots of different routes, how can we know we’re taking the shortest?

We could go out and time ourselves walking every single route but that would require getting out of bed and we’re lazy.

Fortunately, we have Dijkstra’s algorithm which can find us the shortest route between two points. And most importantly, we can do this from the comfort of our bed!

To use Dijkstra’s algorithm, we need to represent our map as a graph of edges (which are like the roads) and nodes (which are like the junctions). Each edge has a value which is the time taken to walk from one node to the other.

When using Dijkstra’s algorithm, you need a start node and a target node. Home will be our start node and school is where we want to go. Seeing as we’re already at home, it takes no time at all to get there. We set the running value to get to the home node as 0. Seeing as it is the lowest running value on the graph, we can say we have discovered the home node and the running value becomes a fixed value.

Next we work out how long it takes to get from home to all of its adjacent nodes and set these as running values. Again we look at our running values and set the lowest value as a fixed value and we can now say this node has been visited.

We look at all of the nodes adjacent to this new discovered nodes and fill in the running values. Remember that running values are the distance from the start node so you have to add all the previous values you needed to get there + the cost of the edge you have just crossed. So 2 + 6 = 8 and so on. Note that running values can be changed if you find a new, lower value.

Repeat the steps like we have done on the previous nodes until the target node, school, becomes the node with the lowest running value. This may happen before all nodes have been discovered.

And there we have it! We now know the shortest route to get us to school so we can maximise our all-important beauty sleep.