What are we talking about here?
This article will deal with perhaps the most widely known work of the Dutch programmer Edsger Wybe Dijkstra. While I can’t help you with the pronunciation of the first two parts of the name, Dijkstra is pronounced ‘dyke – stra’. Dijkstra’s algorithm is a very useful tool to find the shortest distance between any two nodes in a weighted graph. For now we will stick to an explanation of the algorithm, which will be short and to-the-point in keeping with the function of the algorithm. The pseudo-code, python code etc. will appear soon in another article.
Dijkstra’s algorithm is a good way to perform the much sought after task of finding the shortest distance between the source node and all other nodes in a given graph. It can also be modified to find the shortest path between two nodes but more on the implementation next time. If given a graph like the one below, how do we find the shortest distance between our source node(here, ‘0’) and all the other nodes? Think about it…..if you’ve found a way please feel free to skip the rest of this article. However, chances are you haven’t, and think people like Dijkstra have too much time on their hands(my thoughts precisely).
This algorithm requires the usage of something known as a Shortest Path Tree(SPT). For now, the only important thing about SPTs is how we are going to use it in this case. Since in many graphs, a particular node may be connected to the source node in different ways with different distances, it is necessary to find the shortest path from the source to the node and eliminate all other paths. This is something that the SPT is capable of doing. In the following example, we will use the SPT in tandem with a set to keep track of nodes to which the shortest distance has been determined. Parallel to this, we keep updating the shortest distance of nodes from the source as and when we uncover shorter paths. Below is the graph that we will be working with.
The graph comprises 8 nodes and 10 edges(weighted). Now given the source node(here, ‘0’) we start to build our SPT outwards from here with the source as the parent node. First, we add 0 to the SPT set. The shortest distance the source node from the source node is obviously 0. First, we note down the shortest distance(here, above the node for convenience’s sake). Next, we consider the neighbours of 0 and update their shortest paths. These values are subject to change until we decide that we have indeed found the shortest distance. We fix their distances by adding them to the SPT set(or marking them red in the images).
Our next step is to add the closest node not in the SPT set to the SPT set. In this case, the lucky node is 1 with a distance of 5. Next, we update the distances of 1’s neighbours. We do this by simply adding the weight of the edge to the parent node’s distance. This gives us the child node’s distance.
Having done that, we look for the nearest node not present in the SPT set(marked red in the image). Node 7 is clearly the closest node with a distance of 8. Lets mark it red(add it to the SPT set) and proceed to update its children’s distances.
Now, we continue this process of adding the next closest node to the SPT set and updating its children’s distances till we have no nodes remaining. This process is outlined by the rest of the diagrams.
A Different Interpretation
Another way to visualise and understand this algorithm could be to imagine yourself going to different places like a park, a shop, a friend’s house and eventually, your own house. Let’s say you start off at the park. Now, assuming you can only move positive distances(which is true by the way), how would you reason out the closest places from the park? Just a second, a few more conditions – the park is connected to your friend’s house and the shop. Both of these places lead to your house.
If you do it Dijkstra’s way, you first find the place closest to the park. If this is the closest of all neighbouring places, it is follows that even if there are other paths to the place, you will first have to visit one of the other neighbouring places, which is already a greater distance. The same logic is applied for all the remaining places to get the shortest distances.
If you’re interested in coding it, please wait for the next article or refer to the numerous existing articles on the net.