Hello, and welcome. My name is William and today we're going to have a look at some source code for extras shortest path algorithm. Just before we get started, absolutely make sure you watch the previous video where I give all the details of how to implement dextrose and various optimizations we can use to speed up the algorithm. In that video I also discuss two versions of Dykstra algorithm, the lazy implementation and the eager implementation. In this video, we're going to have a look at the eager implementation which is faster. You can also find all the source code and the slides for this video and the last video@github.com slash William slash algorithms there should be a link in the description below.

All right here, we In the source code for textures, shortest path algorithm implemented in the Java programming language, let's have a quick run through. So in this class, I define an edge class which represents a directed edge, you'll notice that this directed edge has a certain cost of taking this edge. And it also has a destination node, which I call to the node, which this edge comes from will be implicitly represented in our adjacency list, so we don't need to take care of that. So when you go and create an instance of this class, you need to specify the number of nodes that are going to be in this graph, and that's the variable and once you know the number of nodes in your graph, you can go ahead and create an empty graph, this simply initializes our adjacency lists. So as you see here, I create Empty ArrayList with n nodes.

And then for each position in the list, I create another list. So this is just an empty Jason c list. This will help us add edges to our graph, which you can do by calling this add edge method. So when you want to add an edge, the graph is specify the node, the edge starts at the node the edge ends at and the cost of taking that edge. Remember that the cost of taking edge cannot be a negative value. All right, and then there's just this convenience method to retrieve the constructed graph.

If ever you want to have a look at that, then here comes the interesting method which actually executes dexterous shortest path algorithm. So in this implementation, I provide a start node and the end. This means we're going to try and go from a starting note index to an end node index. Note that we can also modify Dykstra to give us the shortest distance to every node, not just a specific end node. So there is a way we can just remove this parameter, we don't really need it. But providing the end node allows us to do a small optimization, which is to stop early if we know we've reached that and out, so let's keep it in for now.

So in the slides in the last video, I mentioned that we can use an indexed priority queue to speed up dexterous algorithm and this is exactly what I'm doing below I have an implementation of a min index dare heap which allows us to avoid duplicate nodes in our priority queue. I won't be going over the details of the min indexed theory heap per se, because I already have another video on that in my data structures series. I'll make sure to have a link to that in case you want to check it out. But to construct a Main index theory heap, I compute the degree of how many children each node should have in the heap by dividing the edge count by the number of nodes. And finally inserting that the optimal distance to the start node at the beginning of the algorithm has a distance of zero, which makes sense.

Then I just initialize a few arrays. So this is the distance array, which is going to keep track the minimum distance to each node. So initially, I fill that with a value of positive infinity, and I set that optimal distance to the start node has a value of zero, perfect. And then these are just two supporting arrays that track whether node II has been visited and this prep array is going to be used to reconstruct the shortest path should we ever need to alright let's look at this wild loop which contains the bulk of Dykstra algorithm implementation, so while the priority queue is not empty, we're going to first get the ID of the node with the shortest distance. And we're also going to get the minimum value associated with that node. So while we're at it, we're going to mark that this node is visited so that we don't visit it again in the future.

This line right here, which says that the min value if the minimum value we got from the priority queue is greater than the already optimal distance and the distance array for the node we currently pulled out of the queue. Then we can continue this is because we already found a better path routing through another set of nodes before we got to processing this node, which is fine. The next thing we want to do is get all the edges going outwards from this node so we can reach into our adjacency list and Get all the edges coming out of the current node, then we check if the node this edge wants to go to has already been visited, then we can skip that we don't want to revisit an already visited node, then we compute the new distance of going from the current node to the destination node.

And we do this by reaching into the distance array grabbing the already optimal distance for that node, and adding the edge cost then we try and relax the edge. So we check if the new distance is better than the distance already in the distance array, add the node we want to go to remember that originally, all the indices in the distance array are set to positive infinity. So the first time we visit any node, this condition will always be true, then we just do some housekeeping stuff. So Mark that the optimal distance to get to a certain node came from the current node. We're at also update the distance arrayed have the new optimal distance, then we update our index curlicue? We do this by inserting the cost of going to a node for the first time, or we try and employ a decrease key operation to update the current best distance to that node to be even better.

Then after that loop, we can check if we've reached our end node. And if we have we can return the optimal distance to it. So this is the optimization of returning early. Otherwise, if we've reached the end of the algorithm and the while loop has terminated and the priority queue is empty, then return positive infinity. The rest of this class contains the reconstruct path method in the event that you want to actually reconstruct the shortest path from the starting To the end node, and this is pretty straightforward. Simply give it the start node you want to start at the end node index, then run Dykstra algorithm, make sure that the end node is actually reachable from the start node, then simply loop through the previous array and reverse the path and return it as simple as that.

Well, that's all I got for Dykstra shortest path algorithm. There's also this index theory heap, I'm completely skipping over. Hopefully, that's not too much black magic. But if you are interested and how this priority queue works, make sure to check out my video on it. There should be a link in the description below. So guys, thank you for watching.

Please like this video if you learned something and subscribe for more Mathematics and Computer Science video. Until next time,