Aim :- To find
shortest path
#include <iostream.h>
#include <conio.h>
class graph
{
public:
char a;
char b;
int e;
};
class dijkstra
{
public:
int n,p,t,f;
char c[10];
void get_data();
void
get_connection(graph g[]);
void shortest(graph
g[]);
void
display(graph g[]);
int minm(int
[],int,char []);
int findu(graph
g[],int,int,char []);
};
void
dijkstra::get_data()
{
cout<<"Enter number of nodes in your network:";
cin>>n;
cout<<endl<<"Write the name of each node"<<endl;
for(int
i=0;i<n;i++)
{
cout<<"Name of node "<<i+1<<":";
cin>>c[i];
}
}
void
dijkstra::get_connection(graph g[])
{
clrscr();
cout<<endl<<endl<<"NOW ITS TIME TO CONNECT THE
NODES...!";
cout<<endl<<"Enter 1 if there is connection between
consicutive nodes otherwise enter 0"<<endl;
p=0;
for(int
i=0;i<n;i++)
{
for(int
j=i+1;j<n;j++)
{
cout<<c[i]<<"
& "<<c[j]<<" :";
int
t;
cin>>t;
if(t==1)
{
g[p].a=c[i];
g[p].b=c[j];
cout<<"Enter distance:";
cin>>g[p].e;
p++;
}
}
}
}
void
dijkstra::display(graph g[])
{
clrscr();
cout<<"YOUR NETWORK IS LIKE THIS:"<<endl;
for(int
i=0;i<p;i++)
{
cout<<g[i].a<<" &
"<<g[i].b<<" :"<<g[i].e<<endl;
}
}
void
dijkstra::shortest(graph g[])
{
char s,C[10];
int q,D[10];
cout<<endl<<endl<<"NOW ENTER NODE from which you
want to find shortest distance:";
cin>>s;
t=0;
f=0;
//function
to get distance & node array (Initialization)
for(int
r=0;r<n;r++)
{
if(s!=c[r])
{
C[f]=c[r];
for(int
i=0;i<p;i++)
{
if((g[i].a==s && g[i].b==C[f]) ||
(g[i].a==C[f] && g[i].b==s))
{
D[f]=g[i].e;
q=0;
break;
}
}
if(q!=0)
{
D[f]=32767;
}
f++;
}
} int w,u,v;
//greedy loop
for(q=0;q<n-2;q++)
{
v=minm(D,f,C);
for(w=0;w<f;w++)
{
if(C[w]!=NULL
&& C[w]!=C[v])
{
u=findu(g,w,v,C);
D[w]=(D[w]<(u+D[v])?D[w]:(u+D[v]));
}
}
C[v]=NULL;
}
cout<<"The sortest distance from node
"<<s<<":";
for(int
z=0;z<f-1;z++)
{
cout<<D[z]<<",";
}
cout<<D[f-1];
}
int dijkstra::findu(graph
g[],int w,int v,char C[])
{
for(int
z=0;z<p;z++)
{
if((g[z].a==C[w]
&& g[z].b==C[v]) ||(g[z].a==C[v] && g[z].b==C[w]))
{
return
g[z].e;
}
}
return 32676;
}
int
dijkstra::minm(int j[],int t,char c[])
{
int o=32766,q;
for(int
i=0;i<t;i++)
{
if(o>j[i]
&& c[i]!=NULL)
{
o=j[i];
q=i;
}
}
return q;
}
void main ()
{
clrscr();
graph g[15];
dijkstra d;
d.get_data();
d.get_connection(g);
d.display(g);
d.shortest(g);
getch();
}
Output:
