Question

I want to know the details interpretation of this code for my interview preperation on this code. This is A* algorithm in c++

#include<bits/stdc++.h>
using namespace std;
#define DISCONNECTED -1
int num_of_node,num_of_edge,graph[30][30],pathCost[30];
void init_Heuristic();

struct Node{
    int from,to;
    int cost;
};
struct CompareNode{
    bool operator()(Node& n1, Node& n2){
        if(n1.cost > n2.cost)return true;
        return false;
    }
};
map<int,int>Heuristic;
priority_queue<Node, vector<Node>, CompareNode> PQ;
vector<Node>path;
void AStarSearch(int source,int destination){

    init_Heuristic();
    for(int i = 1; i <= num_of_node; i++){
        if(graph[source][i] != DISCONNECTED){
            Node n;
            n.from = source;
            n.to = i;
            n.cost = graph[source][i] + Heuristic[i];
            pathCost[i] = graph[source][i];
            PQ.push(n);
        }
    }
    while(!PQ.empty()){
        Node tmp = PQ.top();
        path.push_back(tmp);
        if(tmp.to == destination)break;
        PQ.pop();
        for(int i = 1; i <= num_of_node; i++){
            if(graph[tmp.to][i] != DISCONNECTED){
                Node n;
                n.from = tmp.to;
                n.to = i;
                n.cost = pathCost[tmp.to] + graph[tmp.to][i] + Heuristic[i];
                pathCost[i] = pathCost[tmp.to] + graph[tmp.to][i];
                PQ.push(n);
            }
        }
    }
}
int main(){

    int a,b,c,source,destination;

    cout << "Enter Node: " << endl;
    cin >> num_of_node;
    cout << "Enter Edge: " << endl;
    cin >> num_of_edge;
    for(int i=1; i<=num_of_node; i++)
for(int j=1; j<=num_of_node; j++)
   graph[i][j] = DISCONNECTED;

    for(int i = 0; i < num_of_edge; i++){
        cin >> a >> b >> c;
        graph[a][b] = c;
    }
    cout << "Enter source: " << endl;
    cin >> source;
    cout << "Enter destination: " << endl;
    cin >> destination;
    AStarSearch(source,destination);
    for(int i = 0; i < path.size(); i++)
        cout << path.at(i).from << " -> " << path.at(i).to << " = " << path.at(i).cost << endl;
    return 0;
}
void init_Heuristic(){

    ///straight line distance ///

    Heuristic[1] = 10;
    Heuristic[2] = 5;
    Heuristic[3] = 0;
    Heuristic[4] = 13;

}

Answer 1

Consider a square grid having many obstacles and we are given a starting cell and a target cell. We want to reach the target cell (if possible) from the starting cell as quickly as possible. Here A* Search Algorithm comes to the rescue.

What A* Search Algorithm does is that at each step it picks the node according to a value-‘f’ which is a parameter equal to the sum of two other parameters – ‘g’ and ‘h’. At each step it picks the node/cell having the lowest ‘f’, and process that node/cell.

We define ‘g’ and ‘h’ as simply as possible below

g = the movement cost to move from the starting point to a given square on the grid, following the path generated to get there.
h = the estimated movement cost to move from that given square on the grid to the final destination. This is often referred to as the heuristic, which is nothing but a kind of smart guess. We really don’t know the actual distance until we find the path, because all sorts of things can be in the way (walls, water, etc.).