Dijkstra's Shortest Path Run Time

[00:00:00]
>> So let's talk about the running time of this one, cuz it is actually exceptionally complicated. The first time I walked through the running time of this one, I was just like got it, went looked up on the internet I was like, don't got it. And I had to undo it a couple times and really kind of critically think about what happened there.

[00:00:16]
So let's walk through the pseudocode right now and kinda discuss what happens. So the first thing is we have to do these operations right here, right? We have to create our seen array, our previous array and our dist array, correct? Awesome, this obviously means we have to do O(V), right?

[00:00:34]
We have to create these arrays that are V long, okay? Pretty straightforward here. Now, this is something that's kind of interesting. In our case, we're gonna go through worst case every single node, but what is the running time of this function? Right, so this while loop is O(V), right?

[00:00:55]
When we go through every single node once, but what is the running time of this function cuz we call it O(V) times. Well, we go through our entire distance array, or we go through our entire seen array, which means that this function is running time is O(V), which means this while loop checking is gonna be O(V) squared, right?

[00:01:20]
We've now just done something where we're every single time we go to node, we check all other nodes once. That makes sense. The same thing with this one. This is also O(V) squared because we're gonna do this get lowest unvisited check V amount of times and its running time is v amount of checks, cuz it has to go through our entire seen array or entire distance array.

[00:01:46]
Now you know how I initially told you in the beginning yesterday, that the easiest way to look at runtime is just count loops, this is where that is just a complete lie, okay? This is where I miscalculated distedge is the first time cuz you'd probably go O. This is O(E), right?

[00:02:02]
Well, look at that what happened? Right, you'd probably say this is O(E), correct? Because it's going through every edge, right? Then you say well if the while loop is gonna execute O(V) times that means this should be O(V) multiplied by E, correct? Incorrect, my goodness. Okay, so are you ready for the most mind blowing as part about distedge shortest path?

[00:02:27]
Yes, Yes, I'm so excited. Perfect, all right, let's just pretend we have this very simple graph. They are gonna be undirected nodes. So in reality, they are the maximum worst case for dicer, right? Cuz that means every single node has a connection both ways. So if we start here and we visit this node, we are gonna visit each one of the edges once, correct?

[00:02:52]
Then we go to another node we're gonna visit each one of these edges once. Yes, then we're gonna go to the next node, we'll visit each one of these edges once. Then we'll go to the lastly to this node, which will visit each edge once. How many times did we check the edges?

[00:03:09]
We checked it 2E, right, we only went over 2E. We checked each edge twice. So it's actually 2E for the entire thing. So this four loop the reason why it is that way is this four loop is not exhaustive. It doesn't go over every edge in the graph.

[00:03:26]
It goes over every edge that is connected. But if we use an adjacency matrix, and we had the check every single node we would get that terrible running time. But since we have an adjacency list we only check the nodes that were connected to 2, so this becomes o(E) in total, right?

[00:03:45]
That is what we're walking over, so that means our running time would look something like O(V) squared + E, right? We're gonna do that. Lastly, this thing right here is actually just O(1). So it's really fast, we don't even have to think about it. Super duper fast, awesome, right?

[00:04:02]
So that is our running time, in the way we've made it. So now here kind of comes a big culmination of the class. How can we improve the running time of this to be better? Let me say that differently, we need the lowest distance that has not been seen But again Maria, why don't I know?

[00:04:30]
The answer is a minimum heap, right? If we had a minheap, we would literally remove the node, which means we have seen it and it can't be back inside of it. Therefore we don't need to see an array because by the very state of the heap, it has been seen cuz we remove it and B it's always the smallest node at that point.

[00:04:50]
[SOUND] Right, that is awesome, which means that we do need to do something here. And if you remember from earlier update, was that function we didn't write, we'd actually have to call heap update, which needs the use of map to O log or O(1), get the node. Then from there, update it either heap are fining it up or heap are fining it down depending on how the distance was changed.

[00:05:11]
Yeah, yeah, which means that this becomes a log V operation right here. This becomes a log V operation right here and this becomes a log V operation right here which means that we're going to do an E amount of log V. He's so our running time becomes log V multiplied by V plus E which is much better than V squared so there we go we've just done it we've just made something better by simply changing the data structure that we were using Yeah?

[00:05:44]
Everyone's excited? Okay, why do I feel like I'm the only one excited about this? This blew my mind, right, this is fantastic. All right, I thought this was incredible, so this was one of my favorite kind of understandings of data structures is that, A, we broke down a really intense running time.

[00:05:57]
This is a running time that's non-trivial to understand. By simply just drawing out what's happening, we see right away that it's not V times E, it's actually V plus E. It becomes more obvious because we only check the edges once. All right, fantastic, I'm excited, or is everyone else excited?

[00:06:16]
Okay, there's some excitement. We got some excitement going, Kareem, we're gonna need to see some excitement levels. I need to see it go north by at least two. All right, two units of excitement. All right, let's see. It's probably, this dextrose is usually the first algorithm you usually learn after breadth first search and depth of first Search.

[00:06:37]
Apparently, I got so excited I'm going out of order of my notes and there we go. We are now kind of done with the graph section I kept the graph section low cuz as you can see it gets complicated super duper quick. And we did probably the easiest algorithm on graphs as this.

[00:06:52]
We did not do min or max flows ,we didn't do strongly connected components topological sort any of the fun stuff that can exist within the graph realm but it was still pretty radical, I really liked it. I'm super pumped, I'm pumped out of my mind. All right, let's see if there is a part two we will cover some more significantly more complicated fun graphs, any questions here?

[00:07:15]
Do we have any questions here?
>> Are there a lot of graph questions and interviews?
>> Often they're gonna break down like here. Here's a good graph question that I've seen before. And this is one that I have received in an interview. All right, let's pretend that we have a 2D array in which is filled with 1s and 0s, right?

[00:07:38]
0, 1, 0, 0, 1, 1, 1 1, 0, and what I want you to tell me in here, is I want you to tell me how many islands there are. Island is anything in which has a 1 that's connected in any of the four o cordinal direction to another one.

[00:07:56]
So, any contiguous set of 1s. So, that'll be one island, there'd be two islands, the secret here is you use a breadth first or really a depth first search. You can kind of choose which way you want to go. You just simply start right there, mark this thing as seen, increment how many island you've seen add all of these in here and say, hey, are any of you guys 0s?

[00:08:17]
None of you're zeros, I'm done looking. Keep scanning till you hit the next one, we have another island we found, mark this a 0 scan, right, you scan in all four directions. Off the map, off the map, here's another 1,0, going for directions, right? This is a 0 market this as 0 going four directions, blah, blah, blah, going four directions, and there you go.

[00:08:40]
Then you eventually make it to the end of the math. And boom, we just got ourselves done counting the amount of islands we have seen in a graph of 0s and 1s. See graphs, graphs are great. It's just a depth first search. That's all it is. It's just applying a small technique to a depth first search when I heard this question though, even though I knew all these things, my very first thing I thought was, no, I can't do this.

[00:09:05]
And then it turns out it was really simple. I just had to talk myself through it, went through all the data structures I understood and realized that a simple depth for search will get me to all of it or breath for search, whichever one you wanted to do.

[00:09:14]
And I could kind of walk through, cool?