#include<stdio.h>
int **cost,n,*parent,v,*s;
void dijk(int []);
int min(int []);
int main()
{
int i,j;
system("clear");
printf("Enter no.of vertices in graph\n");
scanf("%d",&n);
cost=(int **)malloc(n*sizeof(int *));
for(i=0;i<n;i++)
cost[i]=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("Enter distance between %d and %d\n",i+1,j+1);
scanf("%d",&cost[i][j]);
}
}
int *dist=(int *)malloc(n*sizeof(int));
s=(int *)malloc(n*sizeof(int));
parent=(int *)malloc(n*sizeof(int));
printf("Enter starting vertex\n");
scanf("%d",&j);
v=j-1;
dijk(dist);
}
int min(int a[])
{
int temp=10000,i,j;
for(i=0;i<n;i++)
{
if(a[i]==0)
continue;
else if(a[i]<temp&&s[i]!=1)
{
temp=a[i];
j=i;
}
}
return j;
}
void dijk(int dist[])
{
int i,num,j;
for(i=0;i<n;i++)
{
s[i]=0;
dist[i]=cost[v][i];
if(dist[i]!=1000)
parent[i]=v+1;
else
parent[i]=1000;
}
int ver;
s[v]=1;
dist[v]=0;
for(num=2;num<=n;num++)
{
ver=min(dist);
s[ver]=1;
for(i=0;i<n;i++)
{
if(s[i]==0&&(dist[i]>(dist[ver]+cost[ver][i])))
{
dist[i]=dist[ver]+cost[ver][i];
parent[i]=ver+1;
}
}
}
printf("Paths\n");
printf("PATH\tCOST\n");
for(i=0;i<n;i++)
{
if(parent[i]==v+1)
printf("%d\t%d\n",parent[i],dist[i]);
else if(parent[i]!=1000)
{
printf("%d ",parent[i]);
j=parent[i]-1;
while(parent[j]!=v+1)
{
printf("<- %d ",parent[i]);
j=parent[j]-1;
}
printf("<- %d\t%d\n",parent[i],dist[i]);
}
else
printf("%d node cannot be reachedi\n",i+1);
}
}
No comments:
Post a Comment