MINIMUM SPANNING TREE

FLOYD’S WARSHALL ALGORITHM

#include"iostream.h"
#include"conio.h"
#include"stdlib.h"
#define max 20
class warshall
{
int n,w[max][max],d[max][max],p[max][max];
public:
void getinit();
void floyd();
void path(int,int);
void viewpath();
void dispmat(int);
};

void warshall::getinit()
{
int i,j;
cout<<"enter the no vertices";
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
w[i][j]=0;
cout<<"enter the weight of edges";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j && w[i][j]==0)
{
cout<<"edge"<<>"< cin>>w[i][j];
if(w[i][j]!=99)
w[j][i]=99;
}
}

void warshall::floyd()
{
int i,j,k,d1[max][max],p1[max][max];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
d[i][j]=w[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(d[i][j]==0d[i][j]==99)
p[i][j]=0;
else
p[i][j]=i;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
d1[i][j]=d[i][j];
p1[i][j]=p[i][j];
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(d1[i][j]>(d1[i][k]+d1[k][j]))
{
d[i][j]=d1[i][k]+d1[k][j];
p[i][j]=p1[k][j];
}
else
d[i][j]=d1[i][j];
}
}
}

void warshall::path(int i,int j)
{
if(i==j)
cout< else
{
path(i,p[i][j]);
cout<<"-->"< }
}

void warshall::dispmat(int c)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(c==2)
cout<<"\t"< else if(c==3)
cout<<"\t"< else if(c==4)
cout<<"\t"< }
cout< }
}

void warshall::viewpath()
{
int v1,v2;
cout<<"\nFINDING SHORTEST PATH BETWEEN VERTICES\n";
cout<<"Enter the vertex 1&2 to find shortest path & distance";
cin>>v1>>v2;
cout<<"\nShortest path from"< path(v1,v2);
cout<<"\n The distance of the path is: "<}

void main()
{
int ch;
clrscr();
warshall fw;
do
{
cout<<"\n1-Input 2-weight matrix 3-Distance mat 4-path mat 5- view path\n";
cin>>ch;
switch(ch)
{
case 1: fw.getinit();
fw.floyd();
break;
case 2: cout<<"\tTHE WEIGHT MATRIX\n\n";
fw.dispmat(ch);
break;
case 3: cout<<"\tTHE DISTANCE MATRIX\n\n";
fw.dispmat(ch);
break;
case 4: cout<<"\tTHE PATH MATRIX\n\n";
fw.dispmat(ch);
break;
case 5: fw.viewpath();
break;
case 6: exit(0);
break;
}
}while(ch<=6);
getch();
}