Dijkstra's Shortest Path

[00:00:00]
>> So what is Dijkstra shortest path? Obviously, it is calculating the shortest path from one node to all other nodes in the graph. Which means we can also specifically find it to an individual node as well. Because once you have the full graph marked out, it's very easy just to find that one path from A to B long as you have a previous list.

[00:00:20]
Makes sense? Makes sense, just like our Breadth First Search, we'll be using Breadth First Search for Dijkstra as well. I want to go over Breadth First Search because it requires a previous array because in Dijkstra's we require a previous array. Does that make sense? Awesome, all right, there are a bunch of variations to this and I'll probably program one that sucks, just so you can know that there is one that doesn't suck.

[00:00:47]
Does that sound great? Fantastic, isn't that just the way we always wanna do it? Okay, so let's talk about Dijkstra's shortest path. It's actually a family of what is referred to as a greedy algorithm. So it's actually pretty dang simple. When you write out just the steps that you need to take, you look at it and go, wow, it's actually absurdly simple.

[00:01:07]
Is that not absurdly simple? Okay so let's rewrite a graph that makes some sort of sense I liked that previous graph I wrote, so I'm gonna give it my best effort of how to do that. So we're gonna have this, we're gonna have a 1, we're gonna have a 5, we're gonna have a 1, by the way Dijkstras, non negative weights.

[00:01:28]
So if there's a negative weight you're gonna screw up all of Dijkstras, don't do that, this will be 6 1 7, there we go. So if this is 0,1, 2, 3, 4, the obvious answer is that we go from 0 to 2, to 4, if 0 is our source and 4 is our sync.

[00:01:57]
That makes sense, right? If you just look at the graph, 5 plus 1 is 6, that would be our shortest path. If you go 0 to 1, which is 1, then to 7, that's 8, then to 4. What is that? 9, right, or the other way around. You'd get 7, 8, 9, you get the same answer, right?

[00:02:15]
So our three possible paths for those that don't see that is this which is 6. This, which is 1, 7, 8, 9 or, and then of course through here, which again is 9. So there you go, we see the shortest path 0, 2, 4. So how do we do this?

[00:02:36]
Well, Dijkstras, it's a very clever algorithm, it initially started off as a V-squared running time. But it's gotten a lot better through some sweet optimizations, including one of the data structures we made today makes it into a sweet optimize graph structure or graph search. So first let's look at what's gonna happen here.

[00:02:55]
So the general way we do this is we still have that same previous array because we need to know how to walk it. So we do the exact same algorithm that we did before. We have negative ones all the way in here. So we know with whom have I came from.

[00:03:07]
Second, we need the exact same thing, we can have a seen array depends on the data structure you use. You actually don't need a seen array but we'll have it for now. All right and we'll fill it with a bunch of falses, awesome, right? Lastly, we're gonna need a way to calculate what is the shortest distance.

[00:03:26]
So what we're gonna have, is we're gonna have a distance array and this will be filled with infinities, except for our source node. What is the distance of our source node?
>> Number of nodes?
>> No, zero. Right, if you're already at the place you wanna be, how far do you have to travel?

[00:03:45]
Nowhere, right? It's greatest, right? And so of course we'll put a zero here, we'll pretend our source is the last node, right, just depends on what is passed in. So in our case, it's gonna be 0 for our searching. So we put a 0 at wherever our source is, and we'd also take our seen and make that a true wherever our source is.

[00:04:05]
But again, we don't have to use a seen array if we use the right data structure. So effectively how Dijkstra shortest path works, is that we get the lowest or the nearest unseen node, or unvisited node, meaning at first that's just our source array, right? Because everything else has infinity.

[00:04:28]
So those ones are unvisitable, but our source one is visitable at a distance of 0, right? Right ,so you can imagine one way to do this, is we scan through our distance array. And when we get to zero we're like hey have I seen you yet? I haven't seen you, awesome, we're gonna start with this one cuz this is obviously the smallest distance,let's start right here, cuz the rest of the distance is our infinity.

[00:04:52]
So this is the smallest unseen item. So at that point we would mark it seen. So I'm gonna kind of start right here. So let's pretend this thing has already happened. And then we'll keep doing this, while, and I'm gonna just use a function here, has unvisited. Okay, I'm just gonna use this because I don't wanna give away the game quite yet.

[00:05:15]
So, however we choose to do that could affect how fast our algorithm runs. So right now, we're scanning through every single node effectively by walking through our seen array and or distances array, right? That means you're doing that V amount of times every single time you call that function.

[00:05:31]
Cuz you have to scan them all to find the minimum one you have to scan it all to make sure you have the minimum one that's unseen. All right, so there we go, we have this part done, this is fantastic. Now, what do we have to do? Well, we are gonna get the lowest one.

[00:05:47]
So I'm gonna to call this one low equals get lowest. Right? Get lowest unseen, right? I will put U there for unseen, I don't wanna have to keep writing, way too high and we're gonna mark this one as seen, right? Once we have done this, we've already seen this, we don't need to do it again, awesome.

[00:06:07]
So at this point our first iteration we're currently using the source, right? Perfect, so now what do we need to do? Well, now we need to walk through all of its children and then we need to do something. So let's break this problem down just a little bit.

[00:06:24]
If you think about it, if you look at this graph right here, the shortest distance from zero to one is this link, right? It wouldn't matter however many other links there are, when the only distance I know is this distance, the distance to myself being zero. The next possible shortest distance is this one, right?

[00:06:48]
It wouldn't matter what else the graph looks like it wouldn't matter if this thing had a distance of one, you cannot get any possibly closer right? So, during the first iteration of the graph, we get the source node, which is the closest possible node because it's 0. The next iteration, we are gonna find the closest possible node to the source and that is the shortest distance.

[00:07:10]
No matter how you bake it, that is always gonna be the shortest distance because you can kind of argue that in your own head. If you have an entire series of node and you find the shortest distance from where you start to the next node, that will always be the shortest distance at that point, right?

[00:07:26]
You can never make it any shorter, but then this is where it gets interesting. If you use the distance to that node, plus the distance to all the nodes it's connected to versus the distance to all the nodes I'm connected to. Whatever is the shortest that time becomes the next possible shortest path that is possible in your graph.

[00:07:44]
And that's how Dijkstra work, it just works one at a time, updating the distances for who has the shortest distance where. And so that explanation is not necessarily the best, but code is always really, really good to see that. So let's do this. We're gonna go for edge, in low, right, so that is our current lowest item.

[00:08:07]
I want to walk every single edge. So again, we'll do the same kind of base case checking. If seen, Then continue. Make sense, right? If we've already seen this node, we don't need to look at this node, right? Now, we can just simply move on. All right, so now that we have this edge, we need to do some updating here, right?

[00:08:34]
We need to go okay. If the distance from you or the distance to me plus the distance to you is shorter than any other distance we've seen thus far, we have now found a newer shortest path to that node. Does that make sense? Cuz at first we start with all distances infinity except for the one I'm at, then we say hey out of all the nodes I'm connected to, have we found shorter distances?

[00:09:02]
Well, of course because every distance is infinity, so the nodes you're connected to are instantaneously closer than infinity. And you'll see this as it works out, you'll see how this eventually works. So let's do this. I kinda wanna make this a little bit different. I'm gonna make this just to make this one, I'd say a little bit better.

[00:09:26]
Yeah let's do that, I'm gonna do that just to make this kinda a little bit better cuz I feel like this would just be a better example there. All right, so now that we have this, we have our seen and now we need to calculate its distance. Its distance is gonna be the distances of low, right?

[00:09:45]
The distance it took to get to low, which in our case is 0 for our first node plus the edges weight. Make sense, right? That would literally be the distance at any one point, awesome. If that distance is less than the distances of our last known best distance, ellipses of our edge, right.

[00:10:15]
So say our edge is 1, If there's any other best distances to it then we have now just outperformed it in distances therefore we have found a shorter path to that node. And once we've done that, we can then say it's previous or how it got here of edge Is now low, right?

[00:10:37]
We have now just updated how we got to this node with the shortest possible distance and then we need to update its distance array. To equal our new smaller distance, All right, this of course is also a very magical thing that we can do that can also help make this algorithm run much faster.

[00:11:02]
So if you think about this, what we have right here, we will eventually go through every single node that we are possibly connected to. Getting lowest means that we have any node that has a distance of infinity means it's unreachable based on the node we're at, cuz there are nodes that will be unreachable.

[00:11:17]
You could imagine a situation in which we have something that looks like this right? Node, 7 is right here, it points to 0, but 0 never points to it. So therefore it is literally an unreachable node in this case. There we go, this thing is covered, that is the algorithm of Dijkstra for shortest path.

[00:11:36]
We keep on getting the lowest distance node and then trying to update all the other distances based on this new lowest path we found and it's greedy. So each time you find the shortest path that literally is the shortest possible path within the graph at that individual moment.

[00:11:56]
So there we go. So again, we have to do the exact same thing we've done before, meaning that when we want to build this path, we do need to walk backwards again through, we have our previous array. We start from our needle and then we're gonna have to walk backwards we just got done doing that, we will do it again if we implement Dijkstra shortest path.

[00:12:14]
It's pretty straightforward but I want to kinda talk about something. I'm having a little bit of a battle with myself do we want to implement this first or do we want to discuss its running time first. Let's implement it and then let's talk about his running time, cuz I feel like if we implemented first we're going to see how was done we can discuss that running time then we can discuss how to make it faster