How to write the shortest path code in C…

 

Finding shortest path in C program can be easily understood by taking the real-life example of travelling from a definite destination to another.

Suppose there are two definite destination i.e A and F and you wanted to cover its distance then there must be many multiple directions and paths suppose B,C,D and E all are somehow interconnected to each other then you  still you will search for the shortest path by which you can cover the desired destination of A to F.Similarly in C programming language taking this example we can find the shortest distance for ,reaching our desired destination.This can be easily done by the program mentioned below..

#include <stdio.h>
#include <stdlib.h>
#define size 5
int minpos(int a[size][size],int used[size]);
void dis(int a[size][size],int m,int n);
void shortp(int a[size][size],int p);
int minValue(int x,int y);
void display(int a[size][size]);
int main()
{
int pos=0;
int used[size]={0};
int a[size][size]={{100,10,100,5,100},{100,100,1,2,100},{100,100,100,100,4},{100,3,9,100,2},{7,100,6,100,100}};
display(a);
pos=minpos(a,used);
while(pos!=0)
{

shortp(a,pos);
printf("\nmin is %d\n",pos);
display(a);
pos=minpos(a,used);
}

return 0;
}
int minValue(int x,int y)
{
if(x<y)
return x;
else
return y;
}
void display(int a[size][size])
{
int i,j,x;
printf("%4c",' ');
for(i=0;i<=size-1;i++)
printf("%4c",'A' + i);
printf("\n");
for(i=0;i<=size-1;i++)
{
printf("%4c",'A' + i);
for(j=0;j<=size-1;j++)
{
if(i==j)
{

printf("%4c",'-');
continue;
}
x=a[i][j];
if(x>=100)
printf("%4c",'~');
else

printf("%4d",a[i][j]);
}
printf("\n");
}
}
void shortp(int a[size][size],int p)
{

int i,min;
for(i=0;i<=size-1;i++)
{
if(p==i)
continue;
printf("%d-%d,%d-%d + %d-%d\n",0,i,0,p,p,i);
min=minValue(a[0][i],a[0][p] + a[p][i]);
a[0][i]=min;
}
}
int minpos(int a[size][size],int used[size])
{
int i,pos=0;
int min=a[0][0];

for(i=1;i<=size-1;i++)
{
if(used[i])
continue;

if(a[0][i]<min)
{
min=a[0][i];
pos=i;

}
}
used[pos]=1;
return pos;

}

OUTPUT

Leave a Reply