EX NO:9 IMPLEMENTATION OF DIJKSTRA’S ALGORITHM
AIM:
To write a C-program to implement Dijkstra’s algorithm.
ALGORITHM:
Step 1: Start the program.
Step 2: Include the header files and declare the structure edge which
includes weight ,source vertex and destination vertex
Step 3: In main program read the number of vertices to be created and
also get the adjacent matrix of the directed graph.
. Step 4: After reading the adjacency matrix, print the adjacency matrix
Step 5: Get the source node from the user.
Step 6: Display the predecessor of the each node.
Step 7: Display the distance from source node to every other node.
Step 8: Get the destination node and display the shortest path from
source node to destination node.
Step 9: Print the results.
Step10: Stop the program
.
.
PROGRAM:
#include<stdio.h>
#include<conio.h>
struct edge
{
int vs,vd,wt;
}
a[20];
void dj(int);
int g[20][20];
main()
{
int n,i,j;
clrscr();
printf("\n enter the no. of vertices");
scanf("%d",&n);
printf("\n enter the directed adjancy matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&g[i][j]);
printf("\n the matrix is");
for(i=1;i<=n;i++)
{
printf("\n");
for(j=1;j<=n;j++)
printf("%d\t",g[i][j]);
}
dj(n);
}
void dj(int n)
{
int i,p,j,k=0,st[20],l,sm,t=0,d,pred[20],dist[20],m[20],s;
for(i=1;i<=n;i++)
st[i]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(g[i][j]>0)
{
k++;
a[k].vs=i;
a[k].vd=j;
a[k].wt=g[i][j];
}}}
printf("\n\n enter the starting node:");
scanf("%d",&s);
st[s]=1;
pred[s]=s;
dist[s]=0;
for(i=1;i<=n;i++)
{
if(i!=s)
{
pred[i]=i;
dist[i]=9999;
}}
for(p=1;p<=k;p++)
{
t=0;
for(i=1;i<=k;i++)
{
if((st[a[i].vs]==1)&&(st[a[i].vd]==0))
{
m[++t]=(a[i].wt+dist[a[i].vs]);
}}
sm=m[1];
for(l=2;l<=t;l++)
{
if(m[l]<sm)
sm=m[l];}
for(i=1;i<=k;i++)
{
if((st[a[i].vs]==1)&&(st[a[i].vd]==0))
{
if((a[i].wt+dist[a[i].vs])==sm)
{
st[a[i].vd]=1;
pred[a[i].vd]=a[i].vs;
dist[a[i].vd]=a[i].wt+dist[a[i].vs];
}}}}
printf("\n predecessor \n");
printf("\n\n vertex\tpredecessor\n");
for(i=1;i<=n;i++)
printf("%d\t\t%d\n",i,pred[i]);
printf("\n distance from source node %d",s);
printf("\n\n vertex\tdistance\n");
for(i=1;i<=n;i++)
printf("%d\t\t%d\n",i,dist[i]);
printf("\n enter the destinstion vertex");
scanf("%d",&d);
printf("\n shortest path:");
printf("%d",d);
while(d!=s)
{
d=pred[d];
printf("<-%d",d);
}
getch();
}
