Write a C Program to Implement the Dijkstra’s Shortest Path Algorithm

by

Aim:

To Write a C Program to Implement the Dijkstra’s Shortest Path Algorithm.

Theory:

Dijkstra’s algorithm solves the single-source shortest path problem on a weighted, directed graph only when all edge-weights are non-negative. It maintains a set S of vertices whose final shortest path from the source has already been determined and it repeatedly selects the left vertices with the minimum shortest-path estimate, inserts them into S, and relaxes all edges leaving that edge.

Dijkstra’s Algorithm:

Dijkstra’s algorithm has many variants but the most common one is to find the shortest paths from the source vertex to all other vertices in the graph.

Algorithm:

  • Set all vertices distances = infinity except for the source vertex, set the source distance = 0 .
  • Push the source vertex in a min-priority queue in the form (distance, vertex), as the comparison in the min-priority queue will be according to vertices distances.
  • Pop the vertex with the minimum distance from the priority queue (at first the popped vertex = source).
  • Update the distances of the connected vertices to the popped vertex in case of “current vertex distance + edge weight < next vertex distance”, then push the vertex with the new distance to the priority queue.
  • if the popped vertex is visited before, just continue without using it.
  • Apply the same algorithm again until the priority queue is empty.

Program:

#include<stdio.h>
#define INFINITY 9999
#define MAX 10
void dijkstra(int G[MAX][MAX],int n,int startnode);
int main()
{
int G[MAX][MAX],i,j,n,u;
printf("Enter no. of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
printf("\nEnter the starting node:");
scanf("%d",&u);
dijkstra(G,n,u);
return 0;
}
void dijkstra(int G[MAX][MAX],int n,int startnode)
{
int cost[MAX][MAX],distance[MAX],pred[MAX];
int visited[MAX],count,mindistance,nextnode,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{ if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
}
for(i=0;i<n;i++)
{
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1)
{
mindistance=INFINITY;
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i])
{
mindistance=distance[i];
nextnode=i;
}
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i])
{
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}
for(i=0;i<n;i++)
if(i!=startnode)
{
printf("\nDistance of node%d=%d",i,distance[i]);
printf("\nPath=%d",i);
j=i;
do
{
j=pred[j];
printf("<-%d",j);
}while(j!=startnode);
}
}

Execution:

Input:
5 10 5 8 2 0 9 8 3 7 3 3 5 2 7 0 0 12 14 5 0 16 4 0 2 1 0

Output:

Enter no. of vertices:
Enter the adjacency matrix:

Enter the starting node:
Distance of node1=5
Path=1<-0
Distance of node2=8
Path=2<-0
Distance of node3=2
Path=3<-0
Distance of node4=8
Path=4<-1<-0

Result:

    Thus, Dijkstra’s shortest path algorithm was executed successfully.

Leave a Comment