A* search algorithm
A* fixes this problem. A* lets you tell the computer a guess for how far it will be from each place to the end. The computer can use the guess to tell roughly how far it will take to get from a certain place to Z. Instead of just picking the place nearest to A to look at, it will look at the one which is probably going to have the lowest total. It finds this total by adding the cost to the expected distance left. This way, it can look only in the direction where things will probably get better. It's okay if the guess is not perfect, but even a simple bad guess can make the program go a lot faster. If you're trying to find a path between two places in the real world, a good guess is just the distance between them in a straight line. The real path over roads will be longer, but this lets the program guess it, and it won't go in the wrong direction.