[MUSIC] In the last video, we started looking at Breadth First Search. And what we're gonna do next is apply shortest path algorithms to geographic maps. So in this video, you should be able to represent a geographic map as a graph with more details than we've talked about in the past. And you should be able to explain why Breadth First Search has some limitations when we're working with graphs that have weighted edges. So let's take an example graph, what they have here is essentially some of the cities in the West Coast of the United States focusing in on San Diego and La Jolla which is where we're at. So this is essentially a graph, we have the cities here represented as vertices. We have rows that connect the cities as our edges, and this is essentially a working graph. But if you look at this carefully, you're gonna recognize that there's something essentially missing. What I want you to do is just pause for a few seconds and think about what might be missing from this graph. So when you're thinking about this, you almost certainly identify the fact that this graph is missing distances. In fact, there's kind of this joke within the United States that if you live in the East Coast and you ever visit the West Coast, you think everything on the West Coast is right next to each other. We have friends coming from the East Coast, visiting us in San Diego and they always tell us, while we're there we'll just pop over to San Francisco. San Francisco's a long ways from San Diego, you don't just pop over there and likewise I've done this when I visited a friend in London. I remember telling him I'd really like to go visit Munich and he said the same thing, Munich isn't close to London, it's some distance away. So unless you actually have distances on your graph, we're gonna have some real problems. And we can see this essentially if we pull up a map from Google Maps, you can tell that La Jolla and Tijuana are essentially right next to San Diego, further away is Los Angeles. Way up to the Northwest is San Francisco, and way out to the Northeast is Las Vegas. So what we're gonna do is essentially add these distances to our graph. So what I'm gonna do here then is from San Diego to La Jolla is about 12 miles, so I put 12 there, La Jolla to Los Angeles is 112 miles and so on. And, right now, my distances are strictly miles, but we could do something different if we wanna think about this as essentially the weight of the edge. What I could do to improve this would essentially take into account, say, speed limits. So 112 miles at a 25 mile per hour speed limit is very different than 112 miles at a 75 mile per hour speed limit. Likewise, if you're going to go through Los Angeles on say a Friday afternoon at 4 PM, it's gonna be really really slow because of traffic. So what we might wanna do is augment this to take into account traffic. Lastly, San Diego to Tijuana is a very close distance, but depending on the time of day, trying to cross the border from San Diego to Tijuana can take a fair amount of time. So what we wanna do is essentially augment this graph, and essentially improve it with these other cost metrics. But we'll save that for later, for right now, let's just stick with the distances in terms of just raw miles. My question to you, is if we use Breadth First Search, like we have before, what would I find for essentially the shortest path from San Diego to San Francisco? All right, what I'm hoping in taking the in-video quiz, is that you recognized Breadth First Search is gonna look for the shortest path essentially just in terms of number of edges, not really distances. And as a result, what it's gonna find is a path from San Diego to Las Vegas to San Francisco is two steps away, so essentially the shortest path. But this is a really long distance, this is 901 miles. There's no way, if you're trying to drive from San Diego to San Francisco, that you'd drive through Las Vegas unless you wanted to stop and say, play poker at a casino. If you're gonna go straight from San Diego to San Francisco, you're gonna go through La Jolla, then through Los Angeles, up through Bakersfield and into San Francisco. So, how could I have done better? How could I have made it so I found that shorter path from San Diego through La Jolla through Las Angeles up to San Francisco? Well, we'll figure out how to do that with a new algorithm that's coming next.