Implement Dijkstra's Shortest Path

[00:00:00]
>> So let's go back to our Kata machine and let's go down to Dijkstra's. So this is a DijkstraList. It looks like we're gonna be using an adjacency list, how great is that, and we have to do this. Yes, I have built this before. This is not like I'm gonna come up here and just do this for the first time, that would be just silly of me.

[00:00:18]
So we can use this as kind of our general guide, right? But we do need to implement a couple things, right, which you can imagine has unvisited, is gonna be something we're gonna need to implement. And also get lowest unvisited is also something we're gonna need to implement.

[00:00:35]
Now, something I am gonna do is I'm going to intentionally implement it not the fastest. So for all the people in the chat, they're gonna be like, [SOUND]. Don't do that, let it go, okay? That way, everyone can enjoy the beautiful surprise at the end. So of course, the first thing we need is a seen list again.

[00:00:55]
Cuz again, you don't have a seen list if you use the right data structure, but in this case, we aren't using the right data structure. New array is going to be, of course, the arrays length. It's an adjacency list, which means it represents each one of the nodes and their connection to other nodes.

[00:01:10]
So array length fill(false), awesome, seen(source). We don't even need to do that, we'll do it in the algorithm, awesome. Then we need to go const dist = new Array(arr.length.fill(infinity), right? That means it's just super large number, right? It's unreachable from this point, you don't have to use infinity.

[00:01:33]
But for checking sake, and maybe this is a really large graph that generates a really large value, best probably use infinity, right? All right, so let's go dists[source] = 0, right? This is the smallest distance possible. We're already at the source, therefore awesome, all right? We don't know any other distance yet.

[00:01:55]
We just simply know the distance to the source, which is always going to be 0. And so now, of course, we do the greatest thing ever. Let's create a, we don't actually have to create it. We'll do the Lord's loop, a do while. Now, we don't have to use a do while.

[00:02:10]
In fact, I'm not gonna use the Lord's loop for this one, we're actually just gonna use this. Remember we had two functions in here and I intentionally made them into functions, hasUnvisited and getLowestUnvisited. And the reason why I did that is I wanna hide the data structure that is better.

[00:02:23]
So we will go like this, hasUnvisited, and I'm gonna pass in seen, scenery, right? Sounds good? We could technically also pass a dists array, and so that way it's unseen, but it's distances infinity. Then we go, hey, we can't see this thing. So that makes sense? All right, then we also need to get current, which is going to be getLowestUnvisited, right?

[00:02:49]
And that will be seen and dists again. All right, so we need to implement these two based on the data structures we have currently chosen to use. So let's go up here and go function hasUnvisited, it's gonna take in a Boolean array, correct? Yes okay, awesome scene is gonna be a Boolean array.

[00:03:12]
I always sometimes confuse it with the chicken square, which is boiling, don't do that. All right, so seen array, and then of course dists, which is going to be a number array, correct? Awesome, and let's do a Boolean right here. A boiling, we're gonna get some chicken juices in here.

[00:03:28]
All right, so we have that one. And then let's also do getLowestUnvisited, again, exact same stuff. And we're going to need to return something out this time though. We're gonna want to return out our index that is the slowest unvisited item. All right, we're going to assume in this function that if we're calling it, there is 1.

[00:03:51]
Make sense? Awesome, great, good, let's go. So hasUnvisited, this should be pretty easy, has = false. Look at that, it's has. Why not, for( let i =0, i has to be less than seen. Actually, you know what, we finally have a chance to do this. Let's go, seen.some, whether it's true or not, whether it's seen and its index.

[00:04:16]
So if it's not seen and it's dist, it's less than infinity. I believe that should work. I always forget about infinity. Let's try this, node is infinity less than infinity. [SOUND] It's not less than infinity, good. So if this thing is less than infinity, we should be good, right?

[00:04:41]
That number is obviously less than infinity, perfect. Okay, we found something that does work, perfect. I'm glad they didn't be like, well ,what's your LF of your infinity? I'm glad we don't have to deal with that cuz that would have been harder to do. So there we go, we have our unvisited, we're gonna visit every single scene, and see is there something that's false and its distance is less than infinity.

[00:05:00]
Perfect, so now let's go like this, idx = 0 or we'll go -1. And we'll go let lowestDistance =, gosh, let's do infinity. Yeah, look at that infinity. So now we're gonna walk through all of our distances and see, hey, what is the lowest distance, and it has to be an unseen node.

[00:05:26]
Makes sense? Awesome, for let i = 0, i have to be less than seen.length, ++i. If we've already seen this one, well, we can kinda continue, yeah? Yeah, awesome, good. Great answer everybody. If dists[i] is less than infinity, and, well, actually we don't even need to do that.

[00:05:54]
We kinda make the assumption that no matter, what when we're calling this function, this above case is true. Therefore, this case will eventually happen, it will always be true. So if lowest distance is greater than, if it's greater than this distance, we have found a distance that is smaller, so we're gonna use that one.

[00:06:14]
So lowestDistance = dists[i]. Fantastic, let's do this. And at that point, all we need to do is return out the index in which that happened. So index = i, that's the lowest index, right? We return out the lowest index. Fantastic, we found it, we found the one that's gonna do that.

[00:06:33]
Again, we walk through every single one of these and then return out the lowest one. All right, so now we're at this beautiful point, we've implemented these two. So now the only thing left we have to do is do the rest of this stuff, which isn't too hard.

[00:06:49]
We need to say to the seen, we need to go through every single edge. Long as we haven't seen this edge, we calculate the distance, we technically don't even need to do this haven't seen the edge, because we will be able to use the distance formula to not update.

[00:07:04]
Either way, it doesn't really matter. If we haven't seen this edge, we'll calculate its distance, which is based on my distance plus the distance to that edge. If it's less than its best known distance, we're gonna push both the previous and the dists array with new values. Sounds good?

[00:07:22]
Great, all right, so seen[curr] = true. We have now officially seen this, isn't it just beautiful? Are we just happy we've seen this? It's like Top Gun, it's super good. Actually I haven't seen Top Gun, I'm really excited to see it. All right, so now we need to go through every single edge.

[00:07:39]
I forget, what are we using for edges in here? We are using a weighted adjacency list, which, of course, can be a 2D graph edge. So let's go here and go const adjs =, is it graph? What did I call this thing? Array, terrible naming. All right, so this should be able to give us the list of our edges.

[00:08:03]
So now we can go through each edge. Let i = 0, i has to be less than adjs.length: ++ i. Let's go, and now we can grab out the edge. So first, if seen edge, const edge = adjs[i], so if edge.to, if we've seen this one, we're gonna continue.

[00:08:25]
Wow, that was good spelling. Please tell me you like that spelling, that was. All right, so now we need to calculate its distance. Remember its distance isn't just simply the weight of the edge, but it's the weight of the edge plus my distance. So from the source, everything has a 0 plus their weight.

[00:08:44]
Then we see the next closest one and we adjust all the weights, then we see the next closest one, adjust all the weights. So let's see what we got here. So we go dist = dists from our current item, plus the edge.weight. That is the dist to this node from the node we're at.

[00:09:03]
Make sense? And so if this dist is less than the known dists of the edge, then we need to update. So we can just go dists[edge.to] equals the new smaller disk, and our previous edge.to has a new parent of current. Don't I have to call it pre, what did I call it?

[00:09:27]
I didn't even do a previous. How are you gonna know our way back? We won't, man. All right, there we go, and that should really be the end of it. We'll keep going until we have nothing left to look at. Every single time we pop something off, we mark it as seen, update the possible shortest distance that is known.

[00:09:52]
And then just do that over and over again, getting the lowest possible distance each time. All right, so now all we have left is to just walk our distance backwards and we're done. Again, let me look at the return, my goodness, look at this, I'm a genius. This time we actually just simply did a number array.

[00:10:10]
So as long as there is a pathway from our source node to our sink, we'll have an array with values in it. If there's not, it's just an empty array, fantastic. It's almost as if I've updated this. Okay, yeah, that's the only error, perfect. So let's do that one more time.

[00:10:25]
Again, exact same thing. const out is a number array and it's an empty array. Let current equals our needle, or, in this case, I called it our sink, where we want to go to. And now, we do that same while loop one last time. While previous current does not equal -1, push it into our path, out.push[curr].

[00:10:50]
And then update our current to the parent that got us to this point, curr = prev[curr]. All right, there we go, we're just walking one parent back at a time. Remember, the previous is who was the last person to update our distance to the shortest known path. At this point, we need to do the exact same trick we did before.

[00:11:09]
We don't include the source in this kind of roll up, so we're gonna have to do [source].concat, of course, with something else. Or if we wanna be a little cheeky about it, we could always do one of these, out.push(source), and then just simply out.reverse. Look at that, a little different this time, kinda fun to do.

[00:11:29]
It's always good to change things up, because that way if you get it wrong, you can always blame it on the fact that you changed up live as opposed to just sticking to the script. All right, awesome, this is a lot of code? We did 63 lines of code, including whitespace.

[00:11:45]
And so let's see, did we actually get this thing right? npx jest Dij How was that? It feels good, I'm not gonna lie to you, that feels good.