A*

What is A-star?

A-star is the algorithm solving the single source shortest path question, which combined the Dijkstra and Heuristic Search. That means the A* is Dijkstra with eyes!

How does it work?

We need three functions:

• $dist$: the real distance between start and the current node;

• $h$: the estimate distance between the current node and the end;

• $f$: the total estimate distance between the start and the end;

To inmplement the Heuristic Search, we use the Manhattan Distance which is suitable for the 4-Neighbor Graph \(h(u) = |x_u - x_{\text{goal}}| + |y_u - y_{\text{goal}}|\)

or Euclidean Distance which is suitable for the 8-Neighbor Graph \(h(u) = \sqrt{(x_u - x_{\text{goal}})^2 + (y_u - y_{\text{goal}})^2}\).

Using Dijkstra, We need to use a min-heap based on the $f$ function for the priority queue.

Implement in c++ code

vector<int> x, y; // using Manhattan Distance and initializing in main function
vector<vector<pair<int, int>>> adj;// also init in main function
struct Node{
    int u, f;
};
struct Cmp{
    bool operator()(const Node& a, const Node& b)
    {
        if(a.f != b.f) return a.f > b.f;
        return a.u > b.u;
    }
};
int heuristicManhattan(int u, int end)
{
    return abs(x[u] - x[end]) + abs(y[u] - y[end]);
}
int Astar(int start, int end, int dots)
{
    vector<int> dist(dots, INT_MAX);
    dist[start] = 0;
    vector<int> h(dots);
    for(int i = 0; i < dots; ++i) h[i] = heuristicManhattan(i, end);
    priority_queue<Node, vector<Node>, Cmp> pq;
    pq.push({start, dist[start] + h[start]});
    while(!pq.empty())
    {
        Node cur = pq.top(); pq.pop();
        int u = cur.u; int f = cur.f;
        if(u == end) break;
        if(f != h[u] + dist[u]) continue; // attention please: don't use 'visit' here because the function f(u) = h(u) + dist(u) is not guaranteed to be strictly monotonic.
        for(auto [v, w] : adj[u])
        {
            if(dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                pq.push({v, dist[v] + h[v]});
            }
        }
    }
    return dist[end];