Back to Basics — Divine Algorithms Vol I: Dijkstra’s Algorithm
A Dive into Divinity
The last blog I wrote in the Back to Basics series, we talked about Binary Search Trees. If you missed it, you can check it out right here. For this part of the series, we will shift from data structures to algorithms. One of the algorithms that I personally like is Dijkstra’s Algorithm. This is an algorithm that is used on graphs in order to find the shortest distance from a starting node to a destination node. Don’t worry, for those of you who don’t know much about graph theory and the components in a graph, I will be giving a quick overview of these topics before I explain the algorithm. But first, let’s talk more about the person behind the algorithm.
Who is Dijkstra?
Edsger Wybe Dijkstra was a man of many talents. He worked on things ranging from programming all the way to system science. He was born in the Netherlands and he came from a science and math-oriented family. His father was a chemist and his mother was a mathematician. Dijkstra was originally inclined to pursue a career in law, when his parents encouraged him to study physics and mathematics, not knowing that we would go on to have his name immortalized in the computer science community. After pursuing that career through no sense of intention at all, Dijkstra went along to become the Netherlands' first-ever programmer.
Dijkstra is known for several contributions for his work on algorithms, programming language researches, and several impactful works. However, today, we will be focusing on the work he did in the field of algorithms. Dijkstra came up with an algorithm to find the shortest path between point A and point B in graphs. A fun fact about this algorithm was that he actually came up with the shortest path solution in 20 minutes while he was out with his fiancee shopping!
Now that we have a little background on Dijkstra and his early life, let’s dive more into graphs and graph theory to later explain how his algorithm applies to them. To read more about Dijkstra, other than the Wikipedia links I attached, read this article by him called The Humble Programmer on the ACM Turing Lecture published in 1972.
Another Type of Graph
Okay, so after this refreshing introduction on Dijkstra, let’s dive into the nitty-gritty details.
For most people who work in the business field, when they hear the word graph, they probably think of:
However, if you are more mathematically inclined, you might be thinking about something along the lines of:
If you did think of one of these two graphs, I have some bad news. These won’t be the graphs that we will be talking about today, unfortunately. The graph I will talk about today is the one used in graph theory. This is what it looks like:
To explain this graph, we would have to know some terms first:
1- Vertex/Vertices: Vertices are the graph-equivalent of nodes [Refer to the Binary Search Tree article for reference]. They are connected by lines in the diagram above.
2- Edges: The edges are the lines that connect one vertex to the other. They can either be directed or undirected edges depending on what type of graph it is. The one shown above is an undirected edge since it’s a part of an undirected graph.
3- Undirected: An undirected graph contains undirected edges. Meaning that there is no restriction of the direction of the edges. Think about it in terms of roads while looking at the above diagram. If you want to go from point“0” to point “2”, you can either take roads 3 → 1 or 7 → 2. No restrictions whatsoever.
4- Directed: A directed graph is a graph that contains directed edges. When an edge is directed, it means that it can either exclusively point from one vertex to the other without the possibility of pointing the other way, or, it can be a bi-directional edge, where it allows both directions. Look at the diagram below:
In this diagram for example, if we take the street example, if we want to go from point “A” to point “D” we cannot take the route A → B → D. This is because the “road” from B → D is one-directional from D → B only. The only way to reach from A → D is through the route A → B → C → E → D.
5- Weights: A weighted graph is a graph that has weighted edges. A weighted edge is an edge represented with a numerical value to represent the “cost” of that edge. If we take the street example once again, we can imagine that these weights are the taxes you have to pay for using a road. Ideally, you would want to take the “least expensive road” to your destination.
Now, knowing these terms, it’s time to talk about Dijkstra's’ algorithm!
The Algorithm
The best way to understand the algorithm is to know exactly what it does, show the steps to do it, and every now and then I will be bringing back the analogy of the roads and taxes to pay, in order to make it more clear.
Dijkstra's algorithm is an algorithm that implements the shortest path on both directed and undirected graphs, given that there are no negative-weight edges. The reason you would want to do that is quite obvious, you want the least “cost” while going from the initial starting vertex to the destination vertex. The reason why we want the least cost will be explained later in the use cases. Now, I can explain how the algorithm works
The way it works, on a very high level, is that you start with an initial vertex, the starting point. Other givens you have are the weights of the edges and the destination vertex. The algorithm then proceeds to visit neighboring nodes in order to find the “cheapest” path to the next vertex. After finding that cheapest path, you start doing the same thing again with the current vertex and so on and so forth. Here is the reference graph we will look at together while looking at the steps and solving it with Dijkstra’s algorithm
The steps:
1- You Have a Visitor: Very important preparation step we need to do is that we mark all the vertices as unvisited. Meaning that we have not yet traversed through that vertex, which entails that we have not assigned a total cost to it yet. We add all those unvisited vertices in a set to identify them
2- There is an end to everything: In order to start off, anything really, you have to specify a start and an end. The same applies here. You need to specify a start vertex, a destination vertex, and a vertex on which you are currently on. This current vertex changes the more you traverse through the graph.
3- To Infinity and Beyond: After that, you assign a numerical value to the vertices. Do not confuse that with the ID of each vertex. That numerical value is another value assigned to the vertex to signify the “total cost” needed to travel to that vertex. The reason we set it to infinity is that we want to assume the highest possible value so that if we compare for the first time, the first cost is automatically smaller and that value is assigned. This is for every vertex except the first one, where you assign it to 0, as the start vertex has no total cost to go to.
4- Love Thy Neighbour: For this step, we want to visit all the neighbours of the current vertex that are a subset of the unvisited set. We then see the “cost” of each path from the start vertex to its neighbour vertex.
As we see in the diagram above, we assign a total cost to each vertex, apart from the vertex ID, let’s call it Total Cost. That total cost is the cost of the edge of the vertex that we will be using added to the total cost from the current vertex. For example, if we look above, vertex “1” has cost zero. When we try to go to vertex “6”, we add the weight of the edge from 1 → 6 + the total cost of vertex “1”. We then assign that total cost to the new vertex. The vertex we move to then becomes our current one. After we have successfully visited that vertex we remove it from the unvisited set we once had it in, to ensure we don’t visit that same vertex twice. This same step happens over and over again until we reach the destination vertex.
5- Thanks for The Visit: The only way we can truly know that there is a path from the start vertex to the destination vertex is that if the destination vertex is marked as visited. It is only then that we know when to stop the algorithm, otherwise we keep repeating step 4 until that happens. However, there is a small caveat here. If there is no path that goes from the initial vertex to the destination vertex (usually happens with directed graphs), then we stop the algorithm when the smallest Total Cost amongst the vertices in the unvisited set is infinity
That’s it! Below is a visual representation of how it would look like to run the algorithm that I found on here
Use Cases
From what we have discussed so far, especially after explaining the algorithm, you probably have some idea about what some of the use cases are when it comes to Dijkstra’s. There are two prominent use cases that we actually encounter every day without knowing:
1- Geographical maps: Whenever we use applications similar to Google maps, we constantly get as a top option what the fastest and shortest route for us is. This does not necessarily happen using Dijkstra’s algorithm. But it does happen using a shortest path algorithm, which is a superset of what Dijkstra’s algorithm is. It would also make a lot of sense if we translate the graph components into real-life examples:
Initial Vertex = Current Location
Destination Vertex = Destination Location
Edge Weight = Road Distance
Directed or Undirected = One-way Street or Two-Way Streets
And after translating these components into real-life components, we get a better understanding of how it can be implemented, especially now that we know exactly how the algorithm works
2- Network Routing: With network routing, it's very important that the data packages you send across a network are sent as fast as possible, to optimize the network efficiency. In some implementations, the shortest path algorithm is used in order to find the shortest/fastest route a data package can take.
Now What?
Good question. Now what? Now you explore! You now know a new algorithm that you also found out is being used in everyday implementations. With that information, you can go ahead and try it yourself! There are several open-source codebases on how to implement Dijkstra’s algorithm that you can use, along with a graph visualization, in order to see first hand how this algorithm is implemented programmatically. Not just that, there are other algorithms that implement the shortest path like Prims, A*, Bellman-Ford, and many others. Maybe if you find this interesting, you can go ahead and compare these algorithms and their implementations to Dijkstra. For me, this article was to, potentially, spark a new area of interest in you and trigger you to explore more. So, explore!
Hopefully, you enjoyed reading about this amazing algorithm, and to tease you a bit about the next topic in the Back to Basics series, you will find one algorithm name in the blog that was written quite differently! Let me know what you think, and to reward you for coming this far, here’s a portrait of Dijkstra [not drawn by me!], along with a nice meme for you!
