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 nodes\n ");

scanf("%d",&n);

printf("Enter weight of all the paths in adjacency matrix form\n");

// 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 source\n");

scanf("%d",&source);

printf("Enter the target\n");

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=j-1;i>=0;i--)

{

if(i!=j-1)

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