[MUSIC] In this video we're going to be reexamining breadth first search, and looking at simplifications, essentially, for finding the shortest path through a graph. So at the end of this video you should be able to describe breadth first search's value for unweighted graphs. To do this, we're going to work through an example. What I have here are a number of vertices and edges. We're gonna look for a path between vertex zero and vertex four. So how are we gonna do this? Well if we apply breadth first search, as you already learned from the previous week, what you're gonna find is, I have set up a queue. I'm gonna insert V0 into that queue. And I'm gonna mark that one essentially as distance zero. Distance zero from itself, right, then, what I'm gonna do is I'm gonna remove the zero from the queue. I'm gonna look at all the neighbors of V0 and add them into the queue. So V1 is one away from V to zero so its going to have a distance of one, and we'll mark it as visited and then insert V1 into the queue. Next in line we look at pop and we'll remove V1 from the queue, and then I'm gonna look at its neighbors. So what I'm gonna do is I'm gonna look at V2, I'm gonna say that it has a distance of two because it's one greater than the distance of V1. And the distance of V1 was one, so the distance for V2 is two when market is visited and I'm going to add it to the queue. Next I'm going to look at V4, I'm going to mark this distance as two and I'm gonna realize, wait I'm looking for V4. All right this is the thing I was looking for from the very start. So now that I found it, can I stop now? Are we done? Go ahead and answer this as an in video quiz and we'll come back in just a second. So in your in video quiz I hope you realize we are actually done now. We can stop. But I want to explain why we can stop because understanding why we can stop at this point is going to be essential for developing the next algorithms going forward. So let's think about it this way. So this point in time, after we've pushed V2 onto the queue and we're looking at V4 and we've recognized V4's distance as two, what's going to happen next? So let's mark that point in time, essentially at where we recognized V4's distance is two, and let's just keep it. So the next thing we would have done was push V4 onto the queue, or inserted V4 into the queue. Then we would have looked at V2, we would have removed V2. We would have looked at the neighbors of V2. Marked V3 as a distance of 3 and then inserted V3 into the queue. At this point then we'd keep emptying the queue but you recognize we've already visited all of our nodes so this would actually be pretty clean. But I really want you to pay attention to, is that point in time again, where we found a V4, and we recognized its distance was two. If we label distances for each of these zones in the queue, I think we're gonna understand really clearly, why we could have just stopped right there. So I put these distances here, you're gonna recognize that V0 has a distance of 0, and then they essentially ascend in distance. So that point in time when you saw V4 and you knew its distance was two, the only things that are gonna be added to the queue after that are gonna be as distant or further distant. So we know we've essentially found the shortest path and that's why we're able to stop right then. Now, the big question is, does this work for all graphs? We're gonna find that out in the next video.