/* pgm to implement dijkstra's shortest path algorithm*/
#include<stdio.h>
#define INF 1000
struct Vertex
{
int distance,precd;
int weight[15],visit;
char info;
}v[15];
int n;
void initialize()
{
int i,j;
for(i=0;i<n;i++)
{
v[i].distance=INF;
v[i].precd=-1;
v[i].visit=0;
fflush(stdin);
printf("\n\n\tEnter the Information associated with the vertex %d : ",i+1);
scanf("%c",&v[i].info);
for(j=0;j<n;j++)
v[i].weight[j]=INF;
}
}
int findpath(int s,int d)
{
int current,small,i,k;
int dist;
current=s;
v[s].visit=1;
v[s].distance=0;
while(current!=d)
{
for(i=0;i<n;i++)
{
if(!v[i].visit && v[current].weight[i]!=INF)
{
dist=v[current].weight[i]+v[current].distance;
if(v[i].distance>dist)
{
v[i].distance=dist;
v[i].precd=current;
}
}
}
small=INF;
for(i=0;i<n;i++)
if(!v[i].visit && v[i].distance<small)
{
small=v[i].distance;
k=i;
}
if(small==INF)
{
printf("\n\n\tPATH NOT FOUND\n\n");
return -1;
}
current=k;
v[k].visit=1;
}
return d;
}
void printpath(int c)
{
if(v[c].precd==-1)
printf("\n%3c",v[c].info);
else
{
printpath(v[c].precd);
printf("%3c",v[c].info);
}
}
void main()
{
int i,j,edge,s,d;
char source,dest;
clrscr();
printf("\n\n\t\tPROGRAM TO FIND SHORTEST PATH BETWEEN 2 VETICES\n\n");
printf("\n\tEnter the No.of vertices in the graph : ");
scanf("%d",&n);
initialize();
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(i!=j)
{
printf("\nEnter 1 if there is path exist from %c to %c : ",v[i].info,v[j].info);
scanf("%d",&edge);
if(edge==1)
{
printf("\n\tEnter the Weight : ");
scanf("%d",&edge);
if(edge>0)
v[i].weight[j]=edge;
}
}
}
fflush(stdin);
printf("\n\n\tEnter the Source : ");
scanf("%c",&source);
fflush(stdin);
printf("\n\n\tEnter the Destination : ");
scanf("%c",&dest);
if(source==dest)
{
printf("\n\tSOURCE & DESTINATION CAN'T BE SAME.");
exit(0);
}
for(i=0;i<n;i++)
{
if(v[i].info==source) s=i;
if(v[i].info==dest) d=i;
}
d=findpath(s,d);
if(d!=-1)
{
printpath(d);
printf("\n\tTotal Distance: %d",v[d].distance);
}
getch();
}
Data Structure program to implement Dijkstra's shortest path algorithm
