Hello, and welcome. My name is William. Today we're going to tackle Dykstra shortest path algorithm. This is one of the most important algorithms in graph theory for finding the shortest path on a graph. So without further ado, let's dive right in. The first thing to mention about Dykstra algorithm is that it is a single source shortest path algorithm for graphs.

This means that at the beginning of the algorithm, you need to specify a starting node to indicate a relative starting point for the algorithm. Once you specify the starting node, and execute the algorithm, textures can tell you the shortest path between that node and all other nodes in our graph, which is pretty sweet. So depending on how you input You're dexterous and what data structures are used. The time complexity is typically big O of n log V, which is fairly competitive against other shortest path algorithms we see around. However, before we go crazy trying to find shortest paths on various graphs, you need to know which graphs we are allowed to run dexterous algorithm on. The one main constraint for Dykstra is that all edges of the graph need to have a non negative edge weight.

This constraint is imposed to ensure that once a node has been visited, its optimal distance from the story node cannot be improved any further by finding a shorter path by taking edge with a negative weight. This property is especially important because it enables the extras algorithm to act in a greedy manner by always selecting the next most promising node. For this slide deck. My goal is to help you understand how to implement exercise algorithm and also how to implement it very efficiently. We're going to start by looking at the lazy implementation because it's by far the most common, and then we'll look at the eager implementation of Dykstra algorithm which uses an indexed priority queue alongside the decrease key operation. And lastly, I want to briefly mention how we can use other types of heaps in particular the DA reheat to further boost performance of the algorithm.

At a high level these are the steps required in executing Dykstra algorithm. Note that there are two bits of information we'll need. The first is an array called dist that keeps track of the shortest distance to every node from the start node. Initially, this array can be populated with a value of positive infinity except for the index of the starting node, which should be initialized to zero. Additionally, we'll also need to maintain a priority queue of key value pairs, the key value pairs will be node index distance pairs which tell us which node to visit next, based on a minimum sorted value at the start of the algorithm, we will begin by inserting the key value pair s comma zero into the priority queue, then we'll loop while the priority queue is not empty pulling out the next most promising node index distance pair as we go.

After that, for each node we visit, we will want to iterate over all the outwards edges and relax each edge appending a new node index distance a key value pair to the priority queue upon every successful relaxation. We do this until our priority queue is empty, at which point the shortest distance to each node will be stored in the disk array we are maintaining. So that explanation may have sounded a little bit abstract. Now let's look at an example with some animation to put all the pieces together. In all these examples, assume node zero is always the starting node. Although any node is perfectly fine.

Boxed in red is the distance array, I will be using it to track the optimal distance from the start node to every node in the graph. In the beginning, the distance to every node is initialized to have the value of positive infinity. Since we assume that every node is unreachable if at the end of the algorithm, there's still a value of infinity at a certain index, then we know that that node is unreachable. On the right I will be maintaining key value pairs corresponding to a nodes index and the best distance to get to that node. This priority queue will tell us which node we should visit next, based on which key value pair has the lowest value. Internally priority twos are usually implemented as heaps, but I'm not going to show that visualization here.

To start with assignment distance of zero to the start nodes index, which is index zero in the distance Ray, also insert the key value pair zero comma zero into the priority queue to indicate that we intend on visiting node zero with a best distance of zero, then the algorithm actually starts and we look inside the priority queue for the first time and we discover that we should visit node zero. from node zero, we can visit node one by using the edge with a cost of four. This gives us the best distance of four so we can update the best distance from infinity to four and the dist array, also add this information to the party queue. Next, we can visit node two from node zero just like the last node we can update the optimal distance to reach node two from infinity to one. Additionally add that node two is reachable with a distance of one to the priority queue.

So that concludes visiting all the edges for node zero. To decide to which node we should visit next lectures. Always selects the next most promising node in the priority queue. To do this, simply pull the next best key value pair from the priority queue. node two is the next most promising node because it has a distance of one from the start node, while node one has a greater value of four. from node two, if we take the upwards edge, we can improve the best distance to node one by taking the current best distance from node two, which is one plus the edge cost of two to get to node one for a total cost of three.

This is better than the previous value of four. For every time we find a better distance like this, we insert that information into the party queue. Then we improve the best distance to node three to be six. The next most promising node is node one. We can improve the best distance to node three by taking the edge from node one to node three with a cost of one The next most promising node is node one with value four, but we have already found a better route to get to node one. Since the disk array at index one has a value of three, therefore, we can ignore this entry in the priority queue.

Having these duplicate key entries in the priority queue is what constitutes to making this implementation of Dykstra the lazy implementation because we lazily delete outdated key value pairs. Next up is no three, update the best distance to note four to be seven. We already found a better route to node three, so skip this entry in the priority queue. Finally, visit node four. And that's all for the lazy implementation of dynatrace. There are only a few moving parts but in large, the only things to really keep track of is the distance array which contains the best distance so far.

Far from the start node to every other node, and the priority queue, which tells us which node we should visit next, based on the best value found so far. Let's look at some pseudocode. For how this works, I'll be covering the real source code in the next video. For those interested, this pseudocode runs through Shor's algorithm from a start node and returns the distance array which tells us the shortest distance to every node in the graph. However, it will not tell you which sequence of edges to follow to achieve that optimal distance, this is something that we will need to maintain some additional information for which I will cover as well. So in terms of the variables we'll need in the function definition, I specified three things first is G, the adjacency list of the weighted graph and the number of nodes in the graph and is the index of the start node inside the function.

I begin by in the Using two arrays to keep track of the information we'll need first is a Boolean array called V is short for visited which tracks whether node II has been visited or not. Then I initialize dist the distance array, which will be the output of the function. Make sure you fill the distance array with positive infinity except for the start node, which should be set to zero after this initialize a priority queue that will store the node index best distance pairs sorted by a minimum distance, you should be able to use the built in priority queue in whatever programming language you're using. Remember to insert the start nodes index paired with the distance of zero into the party cute kickstart the algorithm. If you're wondering why there are two sets of brackets, that's because the pair x comma zero is meant to represent a tupple or an object with two values a key and a value.

So while the priority queue is not empty, remove the next most promising Next minimum distance pair and mark that note as visited, then loop over all the neighbors of the current node and skip visited neighbors so that we don't visit them again. Then simply perform the edge relaxation operation. First, compute the distance to the new node, which is calculated by adding the best distance from the start node to the current node, which is found the distance array plus the edge cost of getting to the next node. Once you know that, compare it against the best distance for the next node and update the value if it's better. Then finally insert a new key value pair inside the priority queue. So we visited that node in the future.

So in practice, most standard priority queues do not support a decrease key operation for the built in priority queue. You can think of a decrease key operation as an operation which updates the value of a key in the priority queue. A way to get around this is to add a new node index bestest ns pair every time we need to update the distance. Note as a result, it's possible that we have duplicate node indices in the priority queue like we saw in the animation. This is not ideal, but inserting a new key value pair in logarithmic time is much faster than searching for the key, we want to update in the priority queue, which actually takes linear time. Yes, searching for a key in a priority queue takes linear time because the heap is sorted by the keys values, not the keys themselves.

So effectively, it's like searching in an unordered list for a particular element. A neat optimization we can do which ignores stale, outdated index min distance pairs in our priority queue is to skip them immediately as we pull them from the priority queue. We can do this by checking if the value in the distance array is better than the value in the party queue. And if it is, then we know we have already found a better balance. routing through other nodes. Before we got to processing this note, I'll let that sink in for a little bit.

But this is definitely a neat optimization you'll want to keep around. Now um, I want to talk about finding the shortest path itself, and not just the shortest distance to get there. To do that, we'll need to keep track of some additional information. In particular, we'll want to keep track of the index of the previous node we took to get to the current node. The way to do this is to maintain a previous array I call prev. In the slide, this array tracks the index of the node you took to get to note I initially the previous array should be filled with a sentinel value such as no or minus one.

But as you perform edge relaxation operations, you want to update the previous array to say that the node you're going to came from the node you're currently at, then at the end, instead of returning The distance array also returned the previous array which we will use soon. In another method of perhaps called find shortest path provide all the same arguments with the addition of the end node index and execute the extras to obtain the distance array and the previous array with these two bits of information we can reconstruct the shortest path first check that the end node is reachable by checking that its value in the distance array is not infinity. Then start at the end node and loop backwards through the previous array until you make it back the start node. You know you made back the start node when the value of null is reached.

Since the start node does not have a parent node index, which came from the resulting path of node indices to follow for the shortest path from the start node to the end node will be in the reverse order because we started at the end node and worked backwards. Therefore, we want to make sure we reverse this array before returning the result. Now I want to talk about a few optimizations we can use to make dextrous algorithm more efficient. Sometimes we know the index of our destination node, and don't necessarily need to know the optimal distance to every node in the graph, just that one particular node. So the question is, do we still have to visit every node in the graph just to figure out the distance of that one particular node you want to get to? The answer is yes, we do.

But only in the worst case, which depending on your graph can be somewhat rare. The key realization we'll need to make is that it is possible to stop early once we have finished visiting the destination note. The main idea for stopping early is that dexterous algorithm processes each next most promising note in order. So if the destination node has already been visited, its shortest distance will not change as more future nodes are visited. In terms of code, all we have to do to stop early is check if the current node index is the end node and return early. This can prove to be a very substantial speed up depending on how early you encounter the end node while processing the graph.

Our current implementation of dike shows is what we call the lazy implementation because it inserts duplicate key value pairs and lazily deletes them. This is done because it's more efficient to insert a new key value pair in logarithmic time into the priority queue than it is to update an existing keys value in linear time. The lazy approach works but it is inefficient for dense graphs because we end up with all these stale outdated key value pairs in our priority queue. The eager version of deck shows aims to solve this by avoiding duplicate key value pairs and supporting efficient value updates in logarithmic time using an indexed priority queue. And index priority queue is a priority queue variant which allows Access to key value pairs within the priority queue in constant time and updates in log time if you're using a binary heap. This type of priority queue is extremely useful in many applications, I highly recommend you watch my video on index PDQ to become enlightened.

I'll make sure leave a link in the description, but in the meantime, we'll just assume that we have access to an indexed protocol. Now we're going to take a look at the eager version of Dykstra algorithm where we don't have duplicate keys and particles. So to start with, assign a distance of zero to the start node at index zero in the distance array. Also insert the key value pairs zero comma zero into the party queue to indicate that we intend on visiting node zero with the best distance of zero. Then the algorithm starts and we look inside the priority queue for the first time and we discover we should visit node zero. from node zero we can visit node one by taking the edge with cost five.

This gives us a distance of three So we update the best distance from infinity to five and the distance array also add this information to the priority queue. Next, we can visit node two node zero, just like the last node, we can update the optimal distance to reach node two from infinity to one. Additionally add node two to the priority queue with a distance of one. That concludes visiting all the edges for node zero to decide which node to visit next texture selects the next most promising node in the priority queue. So pull the next best key value pair from priority queue. node two is that next most promising note because it has a distance of one from the start node, which is better than five.

From node two, we can take the sideways edge to improve the best distance to node four to be 13 by taking the current best distance from node two, which is one plus the edge cost of 12 to get to node four, for a total cost of 13. To update the best distance to node one, by taking the upwards edge from node two, notice that I did not insert a new key value pair with a value of one comma four inside the party queue, but rather simply updated the existing value in the party queue from five to four. This is the main difference between the lazy and the eager version. The next most promising node is node one. When taking the downwards edge from node one to node two would discover that node two has already been visited. So we cannot improve is already best distance.

We also cannot improve the best distance no tour by taking the diagonal downwards edge since the total cost of 24 outweighs the best distance of 13 which is already known for that note, however, we can improve the best distance to node three by taking the edge from node one to node three with a car Three alette the animation play, and as it does try and predict what the next move for the algorithm will be. So that's the eager version of Dykstra his algorithm, which I would say is the more proper way of implementing dexterous algorithm. Now let's look at some pseudocode and see what needs to change. First, notice that we're using an indexed priority queue instead of a regular priority queue. Also, notice that we no longer need to wrap our key value pairs as tuples in an object because index party queues have first class support for key value pairs, as opposed to a priority queue which you would Find in your programming languages standard library.

The other thing that needs to change is how we insert value pairs into the party queue. If the key or note index does not yet exist in the index primary key insert it otherwise invoke the decrease key operation to update the best distance to that node in the queue. The operation is called decrease key instead of update because it only updates the value if it is strictly less than the current value in the priority queue. All right, we've looked at several Dykstra optimizations already. But there's one key last optimization I want to talk about. And that is improving the heap we're using.

Currently, we're probably using an indexed binary heap for our priority queue, but we can do better. The thing to notice is that when executing dextrose there are a lot more update operations, especially on dense graphs. Then there are removal operations. Dare heap is a heap variant in which each node has at most D children instead of two, this speeds up the decrease key operation at the expense of more costly removals. So if we look at an example real quick, this is a dare heap with D equals four. Suppose we want to perform an update operation, say we want to perform decrease key for node at index six with a value of one, then we can do the update and then we reposition the key value pair inside the heap.

So we bubble it up, and we bubble it up again, and now it's in the correct position. So that only took a total of two operations. While in contrast, suppose we want to remove the root node, then we swap it with the bottom right node. And then we need to reposition the purple nodes so that it's in position. So we need to look at all The children find the one with the least value and swap it. And the purple note is still not in its correct position.

So again, we need to look at all the children find the one smallest value and swap it. So that took a total of eight operations, which is clearly more expensive. But remember, there are a lot more decreased key operations and Dykstra than there are removals, so this might be beneficial overall. So the question then becomes what is the optimal dare heap degree I should use to maximize the performance of deck shows algorithm? And the answer in general is that the value of d should be equal to the number of edges divided by the number of nodes. This is the best degree to use the balance removals against decreased key operations.

In turn, This improves Dykstra time complexity to be big O of E times log base e divided by V of V Which is better, especially for dense graphs, which have a lot of decreased key operations. The last thing I want to mention is the current state of the art when it comes to choosing the right heat for dextrose algorithm. And right now, the best heap we know of is the Fibonacci heap, which gives Dykstra has algorithm, believe it or not a time complexity of big O of E plus v log V, which is extremely fast. However, in practice, the Fibonacci heap is very difficult to implement and also has a large constant amortized overhead. So it makes them slightly impractical in practice, because your graph has to be very large or you to see the benefit. I have yet to implement one of these.

So I cannot say whether they're that good, but this is just what I've read from other sources. That's all I have for you guys. Right now, thank you so much for watching the implementation source code and slides can be found on GitHub and github.com slash Williams desert slash algorithms. There should also be a link in the description below. Again, thanks for watching and please give this video a thumbs up if you learn something and subscribe for more mathematics and computer science videos. Next video we'll be looking at the source code for everything we talked about in this video.