A* Search Algorithm
A* (said 'A-star') is a smarter way to find the shortest route through a network — a map grid, a road graph, the squares of a video-game level — by adding a sense of direction to the patient search of Dijkstra's algorithm. Plain Dijkstra explores outward in all directions equally, like ripples on a pond, with no idea where the goal sits. A* asks one extra question at every step: roughly how much farther is it from here to the goal? Armed with that hint, it leans its search toward the target instead of wasting effort wandering away from it, usually reaching the goal far faster while still finding a genuinely shortest path.
It balances two numbers for each place it considers. The first is the real cost already spent to get there from the start — the same bookkeeping Dijkstra does. The second is an estimate, called a heuristic, of the cost still remaining to the goal; on a grid this is often just the straight-line or city-block distance, which is easy to compute. A* adds these two together and always expands next the place with the smallest total. So it favours places that are both cheap to reach and seem close to the destination, naturally pushing the search in the right direction.
The catch is the estimate must never overstate the true remaining distance — it must be optimistic, never claiming the goal is farther than it really is. As long as the heuristic stays optimistic in this way (the technical word is admissible), A* is guaranteed to return a shortest path, just like Dijkstra, but with far less searching. In fact, if you feed A* a heuristic that always guesses zero, it collapses back into Dijkstra's algorithm — which is why people describe A* as Dijkstra plus a good hint.
A delivery robot crossing a campus grid uses straight-line distance to the door as its heuristic. Where Dijkstra's algorithm would balloon outward in all directions, A* keeps biasing toward the door, expanding only a narrow corridor of squares, and arrives at the same shortest route after examining a fraction of the map.
Same shortest path as Dijkstra, but A*'s goal-directed hint lets it skip most of the searching.
If the heuristic is allowed to overestimate, A* runs faster but may miss the true shortest path, returning a 'good enough' route instead — a trade-off planners sometimes accept on purpose.