c program to calculate shortest path by dijsktra’s algorithm

How to code work:-

                                 First we take number of node then take input graph in form of adjacency matrix

.Take a array dist[].  dist[i] is the distance of the node i  from the source and initialize all the distance with the maximum value and another array pre[] which is store the previous node.After visiting the first node we run a while loop until the target is not visited and each cycle calculate distance of the node from the source and compare it with the minimum for calculating minimum distance. After visiting the target we will have the shortest path which is  in dist[target].And path in pre[]. 

Code:-


#include<stdio.h>
int main()
{
int cost[10][10],i,j,n,source,target,visited[10]={0},min=999,dist[10],pre[10];
int start,m,d,path[10];
printf(“Enter number of nodesn “);
scanf(“%d”,&n);
printf(“Enter weight of all the paths in adjacency matrix formn”);
// Input graph
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf(“%d”,&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
}
printf(“Enter the sourcen”);
scanf(“%d”,&source);
printf(“Enter the targetn”);
scanf(“%d”,&target);
// logic for dijkstra’s aglorithm
start=source;
for(i=1;i<=n;i++)
{
dist[i]=999; // here we initialize all distances with the maximum value (999) you take any other value also
pre[i]=-1; // pre for the previous node
}
visited[source]=1; // visited source node
dist[source]=0; // distance of first node from first node is 0
while(visited[target]==0)
{
min=999;
m=0;
for(i=1;i<=n;i++)
{
d=dist[start]+cost[start][i]; // calcualte the distance from the source
if(d<dist[i] && visited[i]==0)
{
dist[i]=d;
pre[i]=start;
}
if(min>dist[i] && visited[i]==0)
{
min=dist[i];
m=i;
}
}
start=m;
visited[m]=1;
}
// logic for printing path
start=target;
j=0;
while(start!=-1)
{
path[j++]=start;
start=pre[start];
}
// printing of the path
for(i=j1;i>=0;i–)
{
if(i!=j1)
printf(” to “);
printf(“%d”,path[i]);
}
printf(“n shortest path is %d”,dist[target]);
return 0;
}

Output:-

Enter number of nodes
4
Enter weight of all the paths in adjacency matrix form
0 10 30 100
10 0 10 90
30 10 0 30
100 90 30 0
Enter the source
1
Enter the target
4
1 to 2 to 3 to 4
shortest path is 50

One thought on “c program to calculate shortest path by dijsktra’s algorithm

Leave a Reply

Your email address will not be published.