It's 1956. A young programmer is taking his girlfriend shopping in Amsterdam without knowing that he would develop one of the most important algorithms in history. No one could possibly know that in just 20 minutes the world as we knew it would be transformed. That was the day when a soon-to-be a world-renowned Dutch programmer and mathematician, Edsger W. Dijkstra, came up with an algorithm that would power GPS navigation, network routing, social media networks, supply chains, robotics, and more. He literally changed the world in the time it takes us to drink a cup of coffee. Can you imagine that? Edsger Dijkstra was born in 1930 in Rotterdam, in the Netherlands. [music] He studied mathematics and physics at Leiden University in Leiden, Netherlands. Let's take a look at his algorithm and how he described what happened [music] that day. In 1956, Dijkstra was working as a programmer at the Mathematical Center in Amsterdam. The center was about to unveil a pioneering Dutch computer, the new ARMAC computer. He wanted to showcase the power of this computer by choosing a problem that would be challenging enough to surprise people, but general enough so that people who were not specialized in computing could still understand it and even find it interesting. He chose the problem of finding the shortest path between two locations. He asked, "How can a computer find the most efficient way to get from point A to point B?" He kept thinking about this during and after his work hours. Surprisingly, inspiration came during the most unexpected moment. When Dijkstra and his girlfriend felt tired from walking around the shops that day, they sat down at a cafe terrace to drink a cup of coffee. He kept thinking. He just kept thinking. How could he find the shortest way to travel from Rotterdam to Groningen? The two cities in the Netherlands. He started with that very specific question, but then he realized the potential of making the question more general. Instead of only considering two cities, why not come up with a general solution that would find the shortest path between any two given cities? Surprisingly, in his own words, the solution was a 20-minute invention. 20 minutes, that's all it took. By the time he had finished his coffee, the fundamental logic of what we now know as Dijkstra's algorithm was complete. And the algorithm was not only correct, but also provided the foundation for many of the modern systems that we use nowadays. The algorithm itself was formally published 3 years later in 1959. You can still read the original publication yourself online. It's called A Note on Two Problems in Connection with Graphs. To appreciate what Dijkstra came up with, you need to understand its underlying principles. So, let's dive in. First of all, what is an algorithm? An algorithm is a sequence of very, very specific and unambiguous step-by-step instructions that you follow to solve a problem or reach a solution. Software developers use programming languages to implement these algorithms, making computers follow those instructions step-by-step in a language they understand. To find the shortest path between any two given cities, Dijkstra had to think about the possible paths between the cities in a more abstract way, representing the connections between them and any other cities in the path. He did this by translating the physical world of roads and cities into a data structure called graph. You can think of a graph as a way to represent relationships or connections between things in computer science. Graphs have two main components, nodes and edges. You can think of the nodes as the things that are connected. In Dijkstra's algorithm, nodes represent cities. By viewing the world as a series of nodes and edges, Dijkstra's algorithm can be applied to almost anything, not just roads and cities. They could represent different things in different contexts, users in social media platforms, warehouses in supply chains, routers in computer networks, tiles in video games, and much more. The key takeaway here is that nodes represent things that are somehow connected. These connections are the edges of the graph. But just knowing that the cities are connected is not enough to solve Dijkstra's problem. You need more information than that. Remember that he was trying to find the shortest path between two cities. To find it, to find the shortest path, you need to know the cost associated with each connection or edge. This is known as the weight of the edge. In Dijkstra's problem, weights would represent the distance between two cities or the time it takes to travel between them, an abstract quantity that somehow represents that connection. However, edge weight can have different meanings in different contexts. The number of connections between two users, for example. Color similarity between pixels in different regions of an image. The cost of moving from one tile to another in a video game. And more. When the edges of a graph have weights like these, the graph is classified as a weighted graph. Dijkstra's algorithm works with this type of graph. It uses the weights to find the shortest path. The path with the lowest total weight. Let's see the algorithm in action with a practical example. Imagine you're traveling from source node A to destination node D. And this is the overall connection of the cities or the nodes. Node A is known as the source node, where you're starting the process. The algorithm starts by assigning a distance value to each node. It sets the distance from the source node to itself to zero. And the distance from the source node to all other nodes in the graph to infinity. Infinity is only used temporarily here to represent that the algorithm doesn't know anything about those nodes yet, because it hasn't visited them. Visited nodes are also tracked. Then the algorithm starts by visiting node A, the source node. This is the starting point. It checks its unvisited neighbors. In this case, these nodes, the neighbors, are node B with a distance of two from node A. You can see the distances or weights over here in the diagram. And node C with a distance of six from node A. Since their new distances are smaller than their current distances, remember that we assigned infinity initially, they are updated. Their previous node is also updated to node A. We only update the distances if they are shorter, if we find a better path, a shorter path. Tracking the sequence of nodes, like the previous nodes that we have here in the table, is helpful to recreate the shortest path once we reach the final solution. And finally, in the step, node A is marked as a visited once we check all the neighbors and updated their distances. Then the algorithm visits the next unvisited node with the lowest total edge weight. In this graph, that would be node B, since it's distance from node A is two. So, let's visit node B. We need to check its unvisited neighbors. The neighbors of this node are node A, node C, and node D. But node A was already visited. So, we only consider nodes C and D in this step. Let's start with node C. If we choose a path that goes through node B, the distance from node A to node C would be two plus nine, which is 11. However, in our table, we have a distance of six recorded from node A to node C through a different path that we explored previously. Since taking the path through node B would be longer than what we currently have recorded, we don't update the distance. We just keep the current one. Now, let's go to node D. If we choose a path that goes through node B, the distance from node A to node D would be two plus five, which is seven. This is less than the distance that we currently have recorded. Currently, it is infinity, so seven is definitely better. We update this distance and the previous node to node B. Finally, we mark node B as visited. Now, we need to visit the next unvisited node with the smallest total edge weight. In this graph, that would be node C because its distance is currently six, while the distance to node B from node A is seven. So, let's visit node C. We need to check the unvisited neighbors of node C. Node C has three neighbors: node A, node B, and node D since you can see that it has connections with those nodes. It has edges. However, nodes A and B are already marked as visited. So, we only need to check node D. The distance from node C to node D is eight. The total distance from node A to node D going through node C would be 6 + 8, which is 14. Currently, the distance that we've recorded from node A to node D is seven. So, we just keep the current one. Remember that we're always looking for a better path, a shorter path. If it's not shorter, then we don't update it. And since that's the only unvisited neighbor of node C, we mark it as visited. Finally, we go to the next unvisited node with the lowest total weight. In this case, there's only one unvisited node, which is node D. Since all the neighbors of node D have already been checked and visited, we just mark it as visited. We mark node D as visited. And the algorithm stops since all nodes have been visited and the process has been completed. Now that we have the final result, to find the shortest path from node A to node D, we need to backtrack using the sequence of previous nodes that we've recorded. From node D, we go to node B. And then from node B, we go to node A as you can see here in the table, we're going backwards. So, if we start from node A, the sequence would be node A, node B, and node D. And that's the shortest path from node A to node D in this graph. We did it. Awesome. Great work in this practical part of the video. An important takeaway here is that this algorithm consistently selects the connections with the smallest weights and keeps track of which nodes have been visited and which nodes have not been visited so far. Another important thing that you should know about Dijkstra's algorithm is that it's classified as a greedy algorithm. And you may ask, "Why greedy?" Well, because it's very, very, very greedy. It chooses the best possible option in each step. Basically, it chooses the path that looks best whenever it has to make a decision. Let's dive a little bit deeper and check out a Python implementation of Dijkstra's algorithm to see how you can implement this algorithm in code. Before we dive into the details of the actual Dijkstra function, let's see how you can represent a graph in code, because we will need it. Remember that graphs are the core of this algorithm, the core data structures that represent the cities and their connections in the context of Dijkstra's problem. This is a Python representation of the graph that we have in the diagram. Here, we're using a Python dictionary to represent what we know as an adjacency list, which is basically a dictionary in Python that contains dictionaries. These dictionaries represent which nodes are adjacent to other nodes in the graph. The keys of the main dictionary are all the nodes in the graph, and they are associated to dictionaries that represent the nodes that they are connected to, and the weights of the edges that connect them. For example, as you can see here, node A is connected to node C. And they are connected through an edge of weight six. So, that's how you can interpret these adjacency lists. Great. Now that you know how we'll represent the graph, let's check out the actual function implementation. Let's check out Dijkstra's function implementation. We start by importing a Python built-in module that we will use for creating a priority queue. This is very important because instead of looking through a huge list of cities to find the closest one to the source node once we need to choose which uh cities we will visit next, the priority queue, in this case it will be a min heap because we will prioritize the smallest value, it will keep the city with the shortest distance from the source where the program can have access to it immediately. So, it will keep the values that we are looking for ready to be used in the program. Then, this line defines the function. The function takes two arguments. The graph, which is the data structure that represents the cities and roads, and the source node, also known as the start node. This is the starting point of the whole process. Then, we define the distances variable. This variable stores a dictionary that tracks the shortest distance from the source node to every other node in the graph. Initially, that distance is infinity when it's unknown. Of course, the distance between the source node and itself is zero. So, we initialize that value. Then, we initialize a dictionary that associates every node to its previous node in the path found by the algorithm. Initially, the values are none, but these are updated as the algorithm finds the best path. And we also need a set to store the nodes that have already been visited. Then, we initialize our priority queue, our list of cities or nodes to visit next. This is a list of cities or nodes that we need to visit next. Each city or node is represented by a tuple with its distance from the source node and its name or label. We need the distance because our implementation always looks at the first number in the pair for sorting which nodes we will need to visit next. So, it will sort them based on which cities are closest to the source node, exactly what we need to find the shortest path. After that, we start the while loop that will iterate over the list of cities that we haven't visited yet. Then, we call the heapq.heappop uh method, passing the priority queue, the list of cities that we will visit next as an argument. This will pop the city or it will take the city and then return it with the smallest distance to the source node. Then, we use this index to assign the current distance from the source node to the variable current distance and the name of the current node to the variable current node. If the current node has already been visited, we skip the rest of the iteration. Now that we are at our current node, we need to start moving forward from it to check and update its neighbors. Remember that step from the diagrams? This loop iterates over the immediate neighbors of the current node. Within the for loop, for each unvisited neighbor, the weight of the edge is added to the current distance that has been recorded for that node so far. We basically just add the new edge to the distance to find what could be potentially the new distance from the source node. If the new distance is less than the best distance that we have recorded for that neighbor so far, the distance is updated because that means that we found an even shorter path to the city from the source node. Also, the previous node is updated to track the shortest path. If the path is shorter and we need to update it. And we push that neighbor with its new distance to the priority queue to continue exploring through that path. Once the for loop is completed, we mark the current node as visited by adding it to the set of visited nodes. This is the for loop. And finally, once the while loop, remember that we have a for loop nested within a while loop. Once the while loop is completed because all nodes have been visited, the distances from the source node to every other node in the graph and the corresponding previous nodes for each node are returned. This is the output for the graph. If you need to recreate the shortest path from node A to node D, you can implement a function like this one. It takes the dictionary of previous nodes that we got as the output and the destination node. In this case, the destination was node D. We initialize an empty list for storing the strings that represent the path and a variable to store the current node. We start at the destination. We are basically backtracking. We're going backwards. Then, while the current node is not none because we haven't reached the start of the path, we continue appending the current node to the path and assigning the previous node to the sequence as the current node. We're moving backwards gradually. When the while loop is completed, we reverse the path and return it to get it in the right order from the source node to the destination node. This is an example of how you could call these functions that we've just defined. You can see that we call the Dijkstra function passing the graph as an argument. You can assume that the graph has already been defined in the code. We are passing the source node A. And we are assigning the return value to the variables distances and previous nodes. Then we call the get shortest path function. We pass the previous nodes variable as argument and the destination node D to get the path to node D. And then we print the return values so we can see them better. This will be the output for our graph. The shortest path goes from node A to node B to node D. And the total distance from node A to node D is seven because we would go through an edge of weight two and then an edge of weight five. And that's how this Python implementation works. So let's go back to that famous day because there is something very interesting that you should know. Shall we? You might picture Dijkstra very focused on his coffee table sketching and brainstorming in hundreds of pieces of paper to come up with the right solution, right? Interestingly, that's not how it happened. Dijkstra literally said that he didn't use pencil and paper. [music] He designed it entirely in his head. He said that he learned later that one of the advantages of designing without pencil and paper is that you're almost forced to avoid all avoidable complexities. So, practical takeaway here, designing in your head may help you force simplicity. He was an advocate for simplicity. He approached programming as a high-intellectual challenge. That simplicity combined with the powerful principles of this algorithm is what made this invention one of the greatest developments in history. At that time, Dijkstra didn't know that those 20 minutes would become the cornerstone of his fame, reshaping the world by unlocking capabilities that we didn't even know existed. Every time you find the shortest path to your local grocery store, you're using the power of Dijkstra's algorithm. Dijkstra became one of the most important figures in computer science history. He received the Turing Award in 1972, one of the most important awards in the field. And there's even an annual award named in his honor, the Edsger W. Dijkstra Prize in Distributed Computing. This story proves how inspiration [music] can come from the most unexpected moments, and how brilliant discoveries can have a profound impact in the future of humankind. >> [music] >> Dijkstra literally changed the world with his 20-minute masterpiece. I hope you enjoyed this quick introduction to Dijkstra's algorithm. If you want to go deeper, we have tons of programming and computer science courses on the freeCodeCamp YouTube channel. So, like this video, subscribe, and check out this video that you can see right here.
Generated algorithmically for Search Engine
Indexing.