Dijkstra Algorithm in C Language
Represent a given graph using adjacency matrix and find the shortest path using Dijkstra’s algorithm. Use the map of the area around the college as the graph. Identify the prominent land marks as nodes and find minimum distance to various land marks from the college as the source.
Dijkstra Algorithm in C Language Code
#include
#include
#include
#include
#define MAX 20
#define INFINITE 32767
int *mat(int *,int,char[][20] );
int *freemat(int *);
void shortpath(int *,int,int,int,char[][20]);
int check(char[],char[][20]);
void main()
{
int ch,*visited,s,n,i,n1,*adj,d;
char str[20][20],str1[20];
adj=NULL;
do
{
clrscr();
printf("\n\t\tGRAPH\n\t\t1.ADJANCY MATRIX\n\t\t2.SHORTEST PATH\n\t\t\n\t\t3.EXIT");
printf("\n\t\tENTER UR CHOICE:");
scanf("%d",&ch);
switch(ch)
{
case 1:
if(adj!=NULL)
adj=freemat(adj);
printf("\n\t\tADJANCY MATRIX");
printf("ENTER NO OF NODES");
scanf("%d",&n1);
for(i=0;i<n1;i++) <br=""> {
printf("ENTER PLACE NO %d",i+1);
flushall();
gets(str[i]);
}
adj=mat(adj,n1,str);
break;
case 2:
if(adj==NULL)
printf("ENTER ADJENCY MATRIX FIRST");
else
{
while(1)
{
printf("\n\t\tENTER SOURCE");
flushall();
gets(str1);
s=check(str1,str);
if(s<n1) <br=""> break;
}
while(1)
{
printf("\n\t\tENTER DESTINATION");
flushall();
gets(str1);
d=check(str1,str);
if(d<n1) <br=""> break;
}
printf("SHORTEST PATH IS:");
shortpath(adj,s,d,n1,str);
}
getch();
break;
case 3:
break;
}
}while(ch!=3);
}
int * mat(int *adj,int n,char str[][20])
{
int s,d,w,i;
char so[20],de[20];
adj=(int *)calloc(n,n*2);
while(1)
{
printf("IS THERE ANY EDGES:y/n");
if(getche()=='n')
break;
printf("ENTER SOURCE");
flushall();
gets(so);
for(i=0;i<n;i++) <br=""> {
if(strcmp(so,str[i])==0)
break;
}
if(i==n)
printf("INVALID SOURCE");
else
{
s=i;
printf("ENTER DESTINATION");
flushall();
gets(de);
for(i=0;i<n;i++) <br=""> {
if(strcmp(de,str[i])==0)
break;
}
if(i==n)
printf("INVALID DESTINATION");
else
{
d=i;
if(*(adj+s*n+d)!=0)
printf("ALREADY PRESENT");
else
{
printf("ENTER DISTANCE B/W %s & %s",str[s],str[d]);
scanf("%d",&w);
*(adj+s*n+d)=w;
*(adj+d*n+s)=w;
}
}
}
}
return adj;
}
int *freemat(int *adj)
{
free(adj);
return NULL;
}
void shortpath(int *adj,int s,int d,int n,char str[][20])
{
int *visited,mincost,minver,i,j,k,m=0,*cost,*dest,path[20];
cost=(int *)malloc(2*n);
dest=(int *)malloc(2*n);
visited=(int *)calloc(1,2*n);
for(i=0;i<n;i++) <br=""> *(cost+i)=INFINITE;
j=s;
*(visited+s)=1;
while(*(visited+d)!=1)
{
mincost=INFINITE;
for(i=0;i<n;i++) <br=""> {
if(*(visited+i)!=1)
{
if(*(adj+s*n+i)!=0)
{
if(*(cost+i)>m+(*(adj+s*n+i)))
{
*(cost+i)=m+(*(adj+s*n+i));
*(dest+i)=s;
}
}
if(mincost>=*(cost+i))
{
mincost=*(cost+i);
minver=i;
}
}
}
m=mincost;
s=minver;
*(visited+s)=1;
}
printf("%d",*(cost+d));
getch();
i=d;
k=0;
path[k]=d;
k++;
while(i!=j)
{
path[k++]=*(dest+i);
i=*(dest+i);
}
k--;
printf("PATH IS");
while(k>0)
{
i=path[k];
printf("\n%s\t%s\t%d",str[i],str[path[k-1]],*(adj+i*n+path[k-1]));
k--;
}
getch();
free(visited);
free(cost);
free(dest);
}
int check(char str[],char str1[][20])
{
int s=0;
while(1)
{
flushall();
if(strcmp(str,str1[s])==0)
break;
s++;
}
return s;
}
