SHORTEST Path Finding Algorithm Implementation Program

IMPLEMENTATION OF SHORTEST PATH ALGORITHM

PROGRAM:

#include
#include
#include
class path
{
int a[10][10],c[10][10],key[10][10],num,min,i,j,k;
public:
void findpath();
void read();
void output(int,int);
void out(int i,int j);
};
void path::read()
{
cout<<"Number of rows:";
cin>>num;
for(i=1;i<=num;i++)
for(j=1;j<=num;j++)
{
if(i==j)
a[i][j]=0;
else
{
cout<<"The cost for["<cin>>a[i][j];
}
c[i][j]=a[i][j];
key[i][j]=0;
}
}
void path::findpath()
{
int t1,t2,t3;
for(k=1;k<=num;k++)
for(i=1;i<=num;i++)
for(j=1;j<=num;j++)
{
t1=c[i][k];
t2=c[k][j];
t3=c[i][j];
if(t1!=0&&t2!=0&&(t3==0||t1+t2{
c[i][j]=t1+t2;
key[i][j]=k;
}
}
}
void path::output(int i,int j)
{
min=0;
if(c[i][j]==0)
{
cout<<"No path exist";
return;
}
else
{
cout<<"The path is"<out(i,j);
cout<cout<<"\n";
}
}
void path::out(int i,int j)
{
if(i==j)
return;
if(key[i][j]==0)
{
cout<<"->"<min+=a[i][j];
}
else
{
out(i,key[i][j]);
out(key[i][j],j);
}
}
void main()
{
clrscr();
int ch=1,n1,n2;
path p;
p.read();
p.findpath();
cout<cout<<"2.Exist"<while(ch!=2)
{
cout<cin>>ch;
switch(ch)
{
case 1:
cout<<"Enter the source node";
cin>>n1;
cout<<"Enter the designation node";
cin>>n2;
p.output(n1,n2);
break;
case 2:
exit(0);
}
}
getch();
}

























OUTPUT:

number of nodes3
The cost for[1,2]1
The cost for[1,3]2
The cost for[2,1]3
The cost for[2,3]4
The cost for[3,1]5
The cost for[3,2]6

1,Shortest path
2.Exit

choice...1
Enter the source node1
Enter the destination node2
The path is:1->2
cost is:1

choice...1
Enter the source node3
Enter the destination node2
The path is:3->2
cost is:6

choice...



CIET college Programs,LAB Programs for Engineering Students,Computer Networks LAB Programs,Remoboys,karthik,Remokn,Student3k,TCP programs source code