Program
#include <>
#include <>
#include <>
#define MAX 10
#define UNVISITED -1
#define VISITED 1
#define INFINITY 32767
struct node
{
int prev,len,status;
};
struct node graph[MAX];
int searchpath(int src,int des,int pathmat[MAX],int *minlen);
void viewadjmat();
void viewpathmat(int pm[MAX],int n,int len);
int adjmat[MAX][MAX],n;
char s,d,ch;
int i,j,k,src,des,minlen,tot,pathmat[MAX],tot=0,min,curvetex,newlen,u,v;
void main()
{
FILE *f1;
int cho;
clrscr();
printf("\n\t\t\tDIJKSTRA'S ALGORITHM");
printf("\n\t\t\t--------------------");
printf("\n\nEnter the number of vertices of weighted graph:");
scanf("%d",&n);
if((f1=fopen("z:/ds.txt","rt"))==NULL)
{
fprintf(stderr,"cannot open inputfile");
return;
}
for(i=1;i < =n;i++)
for(j=1;j < =n;j++)
fscanf(f1,"%d",&adjmat[i][j]);
fclose(f1);
printf("The adjacency matrix is:\n\n");
viewadjmat();
while(1)
{
printf("\n Enter the source node");
fflush(stdin);
scanf("%c",&s);
printf("\n Enter the destination node");
fflush(stdin);
scanf("%c",&d);
src=toupper(s)-64;
des=toupper(d)-64;
tot=searchpath(src,des,pathmat,&minlen);
viewpathmat(pathmat,tot,minlen);
tot=0;
minlen=0;
printf("\n Do you want to continue(press 1):");
scanf("%d",&cho);
if(cho!=1)
{
break;
}
}
}
void viewpathmat(int pm[MAX],int n,int len)
{
if(len!=0)
{
printf("minimum length is %d \n\n shortest path is:",len);
for(k=n;k > 1;k--)
printf("%c-- > ",pm[k]+64);
printf("%c\n",pm[k]+64);
printf("\n Distance is");
for(k=n;k > 1;k--)
printf("%d",adjmat[pm[k]][pm[k-1]]);
}
else
printf("\n No path from source to distination");
}
void viewadjmat()
{
printf("\n");
for(i=1;i < =n;i++)
printf("%4c",i+64);
printf("\n\n");
for(i=1;i < =n;i++)
{
printf("\n\n");
for(j=1;j < =n;j++)
{
if(j==1)
printf("%4c",i+64);
printf("%4d",adjmat[i][j]);
}
}
}
int searchpath(int src,int des,int pathmat[MAX],int *minlen)
{
*minlen=0;
for(i=1;i < =n;i++)
{
graph[i].prev=0;
graph[i].len=INFINITY;
graph[i].status=UNVISITED;
}
graph[src].prev=0;
graph[src].len=0;
graph[src].status=VISITED;
curvetex=src;
while(curvetex!=des)
{
for(k=1;k < =n;k++)
{
if(adjmat[curvetex][k] > 0 && graph[k].status==UNVISITED)
{
newlen=graph[curvetex].len+adjmat[curvetex][k];
if(newlen < graph[k].len)
{
graph[k].prev=curvetex;
graph[k].len=newlen;
}
}
}
min=INFINITY;
curvetex=0;
for(i=1;i < =n;i++)
if(graph[i].status==UNVISITED &&graph[i].len < min)
{
min=graph[i].len;
curvetex=i;
}
if(curvetex==0)
return 0;
graph[curvetex].status=VISITED;
}
while(curvetex!=0)
{
pathmat[++tot]=curvetex;
curvetex=graph[curvetex].prev;
}
for(i=tot;i > 1;i--)
{
u=pathmat[i];
v=pathmat[i-1];
*minlen=*minlen+adjmat[u][v];
}
return(tot);
}
DIJKSTRA'S ALGORITHM
------------------------------------
Enter the number of vertices of weighted graph:7
The adjacency matrix is:
A B C D E F G
A 0 2 0 1 0 0 0
B 0 0 0 3 10 0 0
C 4 0 0 0 0 5 0
D 0 0 2 0 2 8 0
E 0 0 0 0 0 0 6
F 0 0 0 0 0 0 0
G 0 0 0 0 0 1 0
Enter the source node: A
Enter the destination node: D
Minimum length is 1
Shortest path is: A-- > D
Distance is: 1
Do you want to continue (press 1):1
Enter the source node: A
Enter the destination node: G
Minimum length is 5
Shortest path is: A-- > D-- > E-- > G
Distance is: 14
Do you want to continue (press 1): 2
DIJKSTRA'S ALGORITHM
