Sunday, December 12, 2010

Floyd Warshall Algorithm

//program to illustrate Floyd Warshall Algorithm

#include
#include
#define inf 9999

class floyd
{
int i,j,n,k,a[20][20],p[20][20],t;

public:
void read();
void process();
int min(int,int);
void display();
};

void floyd::read()
{
cout<<"Floyd Warshall Algorithm\n";
cout<<"------------------------\n";
cout<<"Enter the number of vertices :";
cin>>n;
cout<<"Enter the weighted adjacency matrix :\n";

for ( i = 1;i <= n;i++ )
for ( j = 1;j <= n;j++ )
cin>>a[i][j];

process();
}

void floyd::process()
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(a[i][j]==0)
p[i][j]=inf;
else
p[i][j]=a[i][j];
}

for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
t=p[i][k]+p[k][j];
p[i][j]=min(p[i][j],t);
}
}
}

int floyd::min(int a,int b)
{
if(a return(a);
else
return(b);
}

void floyd::display()
{
cout<<"\nThe Shortest path is\n";

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(p[i][j]==inf)
cout<<"- ";
else
cout< }

cout<<"\n";
}
}

void main()
{
clrscr();

floyd f;

f.read();
f.display();
getch();
}



OUTPUT

Floyd Warshall Algorithm
------------------------
Enter the number of vertices :4
Enter the weighted adjacency matrix :
0 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0

The Shortest path is
- - 12
- 1- -
- - - 1
- - - -

No comments:

Post a Comment