If there's one thing our 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 ways to walk, route, 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 ground. comfort of our bed.
To use Dijkstra's algorithm we need to represent our map as a graph of edges and nodes . 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's the lowest running value on the graph we can say that we have discovered the home node and the running value becomes a fixed value. value.
Next we work out how long it takes to get from home to all its adjacent nodes and we set these as running values. Again we look at our running values and set the lowest value as a fixed value so we can now say this node has been visited. We look at all of the nodes adjacent to this new discovered node 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, plus the cost of the edge you've just crossed, so 2 plus 6 is 8 in this case and so on. Note that the running values are the distance can be changed if you find a new, lower value.
Repeat the steps like we've 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.