It has taken me a while, but I finally feel like I have a solid grasp on Dijkstra's algorithm so I'd like to share my explanation of how to implement it for it today.
Dijkstra was a computer scientist born in the Netherlands who has made many contributions to the field of computer science. One of these nifty ones was an algorithm he invented/discovered, the aptly named, Dijkstra's algorithm. In essence, this nifty tool allows you to find the minimum cost to each point in a graph which allows you to find the shortest path between two points. Now there's plenty of ways to search for the shortest path, but this algorithm in particular deals with weighted paths. Let's imagine that we're trying to the other side of a city. If we knew what roads would take more or less time, we could find the shortest/fastest path to the other side. Some paths may be shorter physically, but have lots of traffic and so will take longer. We can give a weighting to each path and then use Dijkstra's algorithm to find the shortest route.
So with that rough understanding, let's take a deep dive into how the algorithm works. First, we take a weighted graph and add each point/node to a queue. We will call the cost it takes to go from one node to another the path cost. We give each node two values: the cost to use that node, which we initially set to infinity, and the parent node, which we initially set to null. We now set our starting node to have an initial cost of 0. An important thing to note about our queue is that it must always be in sorted order, with the lowest costing nodes at the very start. Once we grab a node we add it to a visited object. Until the queue is empty, we will take the first element in the queue and grab it's neighbors, which is, the other nodes it's connected to.
For each neighbor we need calculate two values and do one check. The first value is the path cost of using this neighbor added to current cost of the node. We compare that to the neighbor's current cost in the queue. If the first cost is less than the second cost, then it's found a cheaper path to the node. That means we set the parent of the neighbor to be the current node and the cost to be the first cost we calculated above. We do this continuously until our queue is empty.
Once every node's been dealt with we'll have a "finished" object with the minimum cost to get to each point. We can use this to find the shortest path by selecting our end point from our finished object and following it's parent. Then we take that parent and follow along to it's parent. And so on and so forth until we get back to our starting point. With that, we'll have a list in opposite order of the shortest path from the endpoint to our starting point.
With all that information in mind, we can essentially implement Dijkstra's algorithm! It was a challenge to fully digest this algorithm and understand what's going on, but it was definitely worth it. Until next time!