CODE :
#include<bits/stdc++.h>
#define mx 1000
using namespace std;
map <string,int>mymap;
map<int,string>mymap1;
int N,E,mat[mx][mx],start,end1,par[mx],cost[mx];
struct node
{
int node_no ;
int huristic_value;
bool operator<(const node& target) const
{
return huristic_value > target.huristic_value;
}
};
node arr[mx];
void Printpath(int V)
{
if(start==V)
{
string s = mymap1[start];
cout << s;
return;
}
else if(par[V]==0)
{
printf("No path exist\n");
}
else
{
Printpath(par[V]);
string s = mymap1[V];
cout <<"-->" << s ;
}
}
int GBFS(int ux)
{
node current;
priority_queue<node>q;
q.push(arr[ux]);
par[ux]=0;
cost[ux] = 0;
while(!q.empty())
{
current = q.top();
int vx = current.node_no;
q.pop();
for(int i=1; i<=N; i++)
{
if(mat[vx][i]!=-1)
{
cost[i]= cost[vx] + mat[vx][i];
q.push(arr[i]);
if(par[vx]!=i)
par[i]=vx;
if(i == end1)
{
return cost[i];
}
}
}
}
}
int main()
{
string s;
int hv;
cout <<"Enter the number of Node : ";
cin >> N;
cout << "N H" << endl;///N for node ;H for huristic value
for(int i=1; i<=N; i++)
{
cin >> s >> hv;
mymap[s] = i;
mymap1[i] = s;
arr[i].node_no = i;
arr[i].huristic_value = hv;
}
cout <<"Enter the number of Edge : " ;
cin >> E ;
string source, des;
int g_n;
for(int i=1; i<=N; i++)
{
for(int j=1; j<=N; j++)
{
mat[i][j] = -1; ///Matrix initialization
}
}
for(int i = 1; i <= E; i++)
{
cin >> source >> des >> g_n;
int x = mymap[source]; ///Input the edges :)
int y = mymap[des];
mat[x][y] = g_n;
mat[y][x] = g_n;
}
for(int i=1; i<=N; i++)
{
par[i]=0;
}
cout << "enter the start and goal node" <<endl;
cin >> source >> des;
start = mymap[source];
end1 = mymap[des];
int path= GBFS(start);
Printpath(end1);
cout << endl << "Path cost : "<<path << endl;
}
INPUT :
8
A 336
T 329
S 253
R 193
F 176
C 160
P 100
B 0
9
A T 118
A S 140
S R 80
S F 99
R C 146
R P 97
F B 211
C P 138
P B 101
A B
OUTPUT :
A-->S-->F-->B
Path cost : 450
No comments:
Post a Comment