Java

Saturday, 18 April 2015

C program to find Shortest path from given data

Program:

 Read: Visit more Html,xml and javascript programs

#include<limits.h>
#include<conio.h>
#define MAXNODE 10
#define PERM 1
#define TENT 2
#define infinity 10
typedef struct NODELABEL
{
int predecessor;
int length;
int label;
}NODELABEL;
int shortpath(a,n,s,t,path,dist)
int a[MAXNODE][MAXNODE],n,s,t,path[MAXNODE],*dist;
{
NODELABEL state[MAXNODE];
int i,k,min,count;
int rpath[MAXNODE];
*dist=0;
for(i=1;i<=n;i++)
{
state[i].predecessor=0;
state[i].length=int;
state[i].label=TENT;
}
state[s].predecessor=0;
state[s].length=0;
state[s].label=PERM;
k=s;
do
{
for(i=1;i<=n;i++)
{
if(a[k][i]>0&&state[i].label)
{
if(state[k].length+a[k][i]<state[i].length)
{
state[i].predecessor=k;
state[i].length=state[k].length+a[k][i];
}
}
min=infinity;
k=0;
for(i=0;i<n;i++)
{
if(state[i].label==TENT&&state[i].length<min)
{
min=state[i].length;
k=i;
}
}
if(k==0)
return(0);
state[k].label=PERM;
}
while(k!=7);
k=7;
count=0;
do
{
count=count+1;
rpath[count]=k;
k=state[k].predecessor;
}
while(k!=0);
for(i=1;i<=count;i++)
path[i]=rpath[count-i+1];
for(i=1;i<count;i++)
*dist t=a(path[i])(path[i+1]);
return(count);
}
void main()
{
int a[MAXNODE][MAXNODE],i,j;
int path[MAXNODE];
int from,to,dist,count n;
printf("how many nodes");
scanf("%d",&n);
for(i=0;i<=n;i++)
{
printf("enter node %d connectivity:",i);
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
printf("\n from to where");
scanf("%d",&from,&to);
count=shortpath(a,n,from,to,path,*dist);
if(dist)
{
printf("\n shortest path:");
printf("%d",path[i]);
for(i=2;i<=count;i++)
printf("%d",path[i]);
printf("\n minimum distance=%d \n",dist);
}
else
{
printf("path does not exist\n");
}
}

No comments:

Post a Comment