A* is an informed search algorithm that combines Dijkstra's guaranteed optimality with a heuristic function h(n) estimating distance to the goal. It minimizes f(n) = g(n) + h(n), where g(n) is the actual cost from start. With an admissible heuristic (never overestimates), A* finds the optimal path faster than Dijkstra.
struct Node{int id;double f;bool operator>(const Node&o)const{return f>o.f;}};
vector<int> astar(vector<vector<pair<int,double>>>& adj, int src, int goal, vector<double>& h) {
int n=adj.size();
vector<double> g(n,1e18); g[src]=0;
vector<int> parent(n,-1);
priority_queue<Node,vector<Node>,greater<Node>> pq;
pq.push({src,h[src]});
while(!pq.empty()){
auto [u,f]=pq.top();pq.pop();
if(u==goal)break;
for(auto[v,w]:adj[u]){
if(g[u]+w<g[v]){g[v]=g[u]+w;parent[v]=u;pq.push({v,g[v]+h[v]});}
}
}
vector<int> path; for(int v=goal;v!=-1;v=parent[v])path.push_back(v);
reverse(path.begin(),path.end()); return path;
}A* evaluates each node by f(n) = g(n) + h(n). g(n) is the exact cost from start to n. h(n) is a heuristic estimate of cost from n to goal. The priority queue always expands the node with the lowest f.
A heuristic is admissible if it never overestimates the true cost. With an admissible heuristic, A* is guaranteed to find the optimal path. Manhattan distance and Euclidean distance are common admissible heuristics.
Dijkstra (h=0 always) explores in all directions equally. A* with a good heuristic focuses exploration toward the goal, visiting far fewer nodes. For grid pathfinding, A* is dramatically faster.
Quiz coming soon for this algorithm.