[MUSIC] In the last video we saw how breadth first search has some limitations when you start with weighted graphs. So what we're gonna do now is start looking Dijkstra's algorithm. How Dijkstra's algorithm is gonna solve the source path problem for again, weighted graph. So by the end of this video you should be able to apply Dijkstra's algorithm. You should be able to write the code to implement Dijkstra's algorithm. You should be able to explain how a Priority Queue works, and how a Priority Queue is used within Dijkstra's algorithm. So looking back, when you first saw breadth-first search code. You recognized that this was using a queue as the main core data structure as part of the algorithm. We also know the algorithm looks something like this. What we're going to now is use a different data structure called a priority queue. Now a priority queue, the analogy here that works quite well is a hospital waiting room. So there's a queue of people waiting to be seen. And maybe these people all have a cold or a flu. But the ambulance shows up and someone's having a heart attack, they get higher priority. They're gonna be seen by the emergency crew a lot faster than the people with just a cold. And this is the way the priority queue works. So it's just like a queue, except each person in the queue has a priority attached to them. So whenever you enqueue an item, you're gonna enqueue the element as well as its priority. And when you dequeue, you're gonna get back the person or the item in the queue that has the highest priority reserved right now. Now, priority queues are actually implemented using Heaps. And you can prioritize either based on low values with Min-Heaps or high values using Max- Heaps. But we're only gonna get into the details of how to design a heap in this module. So now we can start looking at how we're going to change our code from Breadth-forsearch search to now work for Dijkstra Algorithm. First off, we're gonna use a priority queue. So all the places that you saw in Breadth-forsearch that you used a queue. Are now gonna be replaced with operations using the priority queue. We're also gonna have to keep track of essentially the best distance we've seen so far for each node. And I'm gonna initialize that at the very start to be infinity for each of the nodes. Again, I'm gonna be working the priority queue. So we're always gonna be in queuing S, which is a start node. Along with the priority of it, which is zero because it's the start node, into the priority queue. And then as long as the priority queue is empty, we're gonna keep working. And there's some changes here in that you can actually have a single node be in the queue multiple times at different priorities. So what you have to do right at the very start is just to check. Have I visited this node yet? And if you haven't visited the node, you do all the work. If you've already visited the node, this is just a duplicate. You don't do any work. So do that test first. If it hasn't been visited before, now you mark it as visited. We'll still check to see if this is one that we're looking for. Just like we did with breadth-for search. We're still going to go through each occurence neighbors, that aren't in the visited set. Except now we aren't adding to the visited set anymore. Because we do that only if we pop an element from the queue. So that piece has been removed from the breathe of our search. Next we're gonna check if the path the current in is shorter than what we've seen before. So remember we're keeping essentially the best found path to each nodes distance, associated with each node. Again, right now all of them are marked on this map, on this graph as infinity. So if it's better, then we're going to update the distance, potentially update the parent map. And then enqueue, and again, instead of just doing enqueuing a node, we're gonna enqueue the node plus the distance to that node from the start node into the primary queue. Okay, so a lot of changes there. I think this'll make a lot more sense once we start working through the example. So what we gonna try to do is we're gonna start with essentially no V0. That's our start node. We're gonna initialize it's distance to the node, V0 to V0, and we're gonna insert into the prior enqueue, again, is that pair of V0 and the distance of zero. Vertex, distance for each time in the priority queue. Next we're gonna remove V0 from the priority queue and we're gonna make that the current node that we're looking at. And when I'm doing this in these slides I'm gonna always mark the current node as essentially the red one. First thing we're gonna do is because V0 hasn't been visited before, we're gonna mark it now as visited. And I want to mark it as visited by making it blue. Next I'm gonna look at all the neighbors of V0 and find that V0 has an edge to V1. And its distance is gonna be two. And the reason I know its distance is two is because the distance to V0 is zero. The edge weight from V0 to V1 is two. You add those and you get a distance of two. In doing so I'm gonna mark the distance of V1 to V2. And I'm gonna insert into the priority queue V1 with a distance of two. Next we're gonna remove V1,2 from the priority queue. We're gonna make current be V1. Just like before, V1 hasn't been visited before. So I'm gonna mark it as visited. And then I'm gonna start looking at its neighbors. So first thing I'm gonna do is, I'm gonna recognize that V2 can be reached at a distance of three, not a distance of infinity. And the reason I got three is that the distance to V1 is two and the edge from V1 to V2 has a weight of one. So two plus one is three. I'm then gonna look over to V4 and recognize I can reach V4 with a distance of eight. And again, the reason I know I can reach it with a distance of eight is because I have V1's distance is two, and the edge from V1 to V4 is six. If you sum those, you get eight. And then when I add both the {V2, 3}, we already did that, as well as {V4, 8}. And again, recognize that the larger distances here are gonna have a lower priority. So V2, 3 is essentially at the front of the list because it's priority is three. Next, we're going to go to the next node. So we're gonna remove V2 from the list. We're gonna mark that as our current. And just like before, because V2 hasn't been visited before, I am going to mark it now as visited. And now I am going to look at the edges from V2. And I'm gonna see that I have a way from going V2 to V3 as a distance of five. So, I'm gonna update that infinity, change it over to be five. And we're gonna insert V3, 5 into the priority queue. Because five is less than eight, it's gonna be pushed to the very front of the queue, even though V4 has been in there longer. So again, we're basing this on priority, not how long the element's been in the queue. At this point, we're essentially done with V2, so we're going to go to the next step, which would be to remove V3 from the queue. Make V3 the current node because V3 hasn't been visited, we're gonna mark it as visited. And then, we'll look at the neighbors of V3. And we'll see that five plus one, the distance from V3 to V4, through the path from V0 to V1 to V2 to V3. Is shorter than the previous distance of eight, that V4 was marked with. So what I'm gonna do then is change that eight to be a six. And I'm gonna enqueue that into the priority queue. So now we have {V4, 6} being inqueued into the queue, it takes a higher priority, because 6 is less than 8 I wanna point out at this point we have two entries for V4 in the queue. Well that's totally okay. If you remember right at the start of this video. I said we add this extra clause, which was to say if you DQ an element you check, has it been visited before? If it already has, you don't do anything. So it's okay for us to have multiple entries for V4, essentially, in our queue. That's totally okay. Next thing I'm gonna do is I'm gonna remove V four comma six from the queue. Make V four our current node. I'm going to mark V four as visited because it hasn't been visited before. And we're done. We found our source path from V four, from V zero to V four to have a distance of six. And just like when we talked about looking at BFS. We don't need to look at anything else in this cue. Because everything that's in the cue after this is gonna have a higher distance. So we have a larger distance, we don't need to look at those anymore. One thing I haven't covered through this video, and I know there's a lot of details that we just worked through. I didn't work through the details on how to obtain that parent HashMap. And I want you to think through that on your own. Because you're essentially gonna be doing this code for the assignment this week. Good luck.
