Senin, 22 September 2014

IMPLEMENTATION OF SHORTEST PATH ALGORITHM

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


0 komentar:

Posting Komentar

Blog Archive