AStar.cpp
1: #include<iostream>
2: #include<stdlib.h>
3: #define MAX 200
4: using namespace std;
5: int hn[MAX]={-1};
6: int n; // no. of vertices
7: int src, dest; // source & destination nodes
8: struct node
9: {
10: int data;
11: int cost;
12: struct node *next;
13: };
14: void append(struct node **head, int data, int cost)
15: {
16: struct node *temp = (struct node*)malloc(sizeof(struct node));
17: temp->data = data;
18: temp->cost = cost;
19: temp->next = NULL;
20: if(*head == NULL)
21: {
22: *head = temp;
23: }
24: else
25: {
26: struct node *tmp = *head;
27: while(tmp->next != NULL)
28: tmp = tmp->next;
29: tmp->next = temp;
30: }
31: }
32: int min(int *arr, int size)
33: {
34: int k = arr[0], l=0;
35: for(int i=1; i<size; i++)
36: {
37: if(arr[i] < k)
38: {
39: k = arr[i];
40: l = i;
41: }
42: }
43: return l;
44: }
45: void a_star(struct node **arr)
46: {
47: struct node *temp;
48: int x=0, y=0, path[n], cost[n];
49: cout<<"\n\n";
50: cout<<"Optimal Path: \n";
51: cout<<"--------------\n";
52: cout<<src<<" ";
53: while(path[x-1] != dest)
54: {
55: int i=0, j=0, v[n], fn[n];
56: for(temp = *(arr+src-1); temp; temp=temp->next)
57: {
58: fn[i++] = temp->cost + hn[temp->data-1];
59: v[j++] = temp->data;
60: }
61: j = min(fn, i);
62: path[x++] = src = v[j];
63: cost[y++] = fn[j] - hn[v[j]-1];
64: }
65: int i=0;
66: int cst=0;
67: while(i<x)
68: cout<<path[i]<<" ", cst+=cost[i++];
69: cout<<"\nOptimal Cost: \n";
70: cout<<"--------------\n";
71: cout<<cst;
72: cout<<"\n\n";
73: }
74: int main()
75: {
76: cout<<"\n\nEnter no. of vertices: ";
77: cin>>n;
78: int mat[n][n];
79: struct node *arr[n];
80: cout<<"\n\nEnter Adjacency Matrix of size ["<<n<<"x"<<n<<"]: \n";
81: cout<<"--------------------------------------\n";
82: for(int i=0; i<n; i++)
83: {
84: for(int j=0; j<n; j++)
85: {
86: cin>>mat[i][j];
87: }
88: }
89: for(int i=0; i<n; i++)
90: {
91: arr[i] = NULL;
92: for(int j=0; j<n; j++)
93: {
94: if(mat[i][j] > 0)
95: {
96: append(&arr[i], j+1, mat[i][j]);
97: }
98: }
99: }
100: cout<<"\n\nEnter values of h(n): ", cout<<"\n----------------------";
101: for(int i=0; i<n; i++)
102: cout<<"\nh(n) of vertex "<<i+1<<" : ", cin>>hn[i];
103: label:
104: cout<<"\n\nEnter source & destination: ", cout<<"\n----------------------------";
105: cout<<"\nEnter source vertex: ", cin>>src;
106: cout<<"\nEnter destination vertex: ", cin>>dest;
107: if( src > n || dest > n)
108: {
109: cout<<"\nPlease enter valid nodes !!";
110: goto label;
111: }
112: a_star(arr);
113: return 0;
114: }
