[MUSIC] In the last video we saw a very powerful algorithm known as Dijkstra's algorithm, and it's quite useful in finding the shortest path between one node and another in a weighted graph. In this video we're gonna explore a more advanced algorithm called the A* search algorithm. So at the end of this video, you should be able to describe the limitation of Dijkstra's, and then apply A* algorithm to a weighted graph. And then you should be able to write the code for an A* search algorithm. So let's go back to our original problem. Let's say we're trying to get from San Diego to Seattle. How would I get driving directions there? Well, I know from having both lived in Seattle and San Diego that you just drive I-5. You're gonna take I-5 up through Los Angeles, up through Sacramento, up through Portland, and get straight to Seattle. And if you do a search on Google Maps, you'll find the same thing, that this is about 1,255 miles. Now, Dijkstra's algorithm if applied to the graph would actually find this just fine, it would find us the shortest route. But I have some questions about how it's gonna find that route. So when we use Dijkstra what it's gonna do is it's gonna start at San Diego and it's gonna start exploring out. It's gonna keep looking until it can find Seattle. It's gonna explore out, out, out, and then eventually find Seattle. And that's okay, except in the path to finding a route from San Diego to Seattle, it's gonna have explored a route through Denver, Colorado, through Dallas, Texas, and even through Mazatlan, Mexico. And, if you were planning your own route from San Diego to Seattle there's essentially no way will you look in Denver, or Dallas, or Mazatlan. What I want you to do is take a few seconds and think about why you would have never considered Dallas, and I'll see you back in just a second. All right, my hope is that you said something along the lines of well Dallas is going the wrong direction, right? I'm headed east and east isn't going to help me get any closer to Seattle. In fact, by going all the way out to Dallas, I've made my distance from Seattle even further than I started. In fact, the straight line distance, essentially as a crow flies, from San Diego to Seattle is 1064 miles, and going all the way out east to Dallas actually made me further away. I'm now 1680 miles away. So, what should we have done differently? Well, Dijkstra only considers the distance from the source, from San Diego, on its way to try to find Seattle, but what we really want to do is also consider how far away we are from the target as well. Now we're working with Dijkstra's algorithm. What we had was a priority queue that has ordering based on essentially g(n), where g(n) is the distance from the start vertex to my end vertex. To change the to the state A* search algorithm, all we're gonna do is add a second component which is called h(n). Gonna be the heuristic estimated cost from vertex n to the goal vertex. And all we're thinking here, the g(n) is essentially gonna be the distance from the start to my current vertex. And then h(n) is my guess as to how much it's gonna cost to get from vertex n to the goal, or my distance from the target. I'm just gonna sum those and that's gonna give my function that I wanna use for the priority queue. Now a couple of pieces to this. The first is that you really see Dijkstra as a special case of the A* search algorithm where h(n) is just essentially zero. The second thing I want to point out is you're guaranteed to find the shortest path still In this graph only if the heuristic estimated cost is never an overestimate. So you want to make sure it's always an underestimate. And this works really well for geographic data. Because we can essentially just use that straight line distance as an underestimate. You can't get any faster than if you fly essentially straight there just as a crow would. And that's essentially all we need to do to change the A* algorithm. What I want to do is real quickly show what this might look like during a real search. You start at San Diego and you essentially just start exploring out from San Diego, but closer to Seattle. You're gonna go up by five and you're going to go through LA. You're going to keep going all the way through Sacramento. I want to point out at this point I'm looking at Sacramento, but I haven't looked at Las Vegas yet, even though Sacramento is further from San Diego than Las Vegas is, and the reason for that is we'd have to look at the equation itself. So for Sacramento, F of N is going to be 504. That's the distance from San Diego to Sacramento. Plus 625, where 625 is the straight-line distance from Sacramento to Seattle. Las Vegas, on the other hand, its function is 331, which is the distance from San Diego to Las Vegas plus 871, which is that straight-line distance from Las Vegas to Seattle. So even though Las Vegas is closer than Sacramento I'm not gonna look at Las Vegas before I look at Sacramento because Sacramento is essentially a higher priority because it has a lower distance. So A * search algorithm is really just a minor change to the code that you already wrote for Dijkstra and all you're gonna do is just change the priority function.