#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
class dij
{
int graph[15][15],s[15],path[15],mark[15],vertex,source,i,j,u,pre[15],count;
public:
dij()
{
count=0;
}
int min(int a[],int m[],int k);
void print(int,int,int[]);
void getgraph();
};
void dij::getgraph()
{
cout<<"Enter the no of Vertices\t";
cin>>vertex;
if(vertex<=0)
{
cout<<"Meaningless Option\n";
exit(1);
}
cout<<"\n\n\t\tEnter the Weighted Adjacent Matrix\n";
for(i=1;i<=vertex;i++)
{
for(j=1;j<=vertex;j++)
{
cout<<"\nEnter the elments of "<<i<<","<<j<<"\t";
cin>>graph[i][j];
}
}
cout<<"\n\n\tEnter the source vertex\t";
cin>>source;
for(j=1;j<=vertex;j++)
{
mark[j]=0;
path[j]=999;
pre[j]=0;
}
path[source]=0;
while(count<vertex)
{
u=min(path,mark,vertex);
s[++count]=u;
mark[u]=1;
for(i=1;i<=vertex;i++)
{
if(graph[u][i]>0)
{
if(mark[i]!=1)
{
if(path[i]>path[u]+graph[u][i])
{
path[i]=path[u]+graph[u][i];
pre[i]=u;
}
}
}
}
}
for(i=1;i<=vertex;i++)
{
cout<<"\n";
print(source,i,pre);
if(path[i]!=999)
cout<<"-->"<<path[i];
}
}
int dij::min(int a[],int m[],int k)
{
int mi=999;
int i,t;
for(i=1;i<=k;i++)
{
if(m[i]!=1)
{
if(mi>=a[i])
{
mi=a[i];
t=i;
}
}
}
return t;
}
void dij::print(int x,int i,int p[])
{
cout<<"\n";
if(i==x)
{
cout<<x;
}
else
{
if(p[i]==0)
cout<<"No Path from "<<x<<"to "<<i;
else
{
print(x,p[i],p);
cout<<".."<<i;
}
}
}
void main()
{
dij d;
clrscr();
cout<<"\n\t\t\tDIJKSTRA'S ALGORITHM\n\n";
d.getgraph();
getch();
}
Comments
Post a Comment