dijkstra's algorithm in c code example

Example 1: dijkstra algorithm using c

#include<stdio.h>
#include<conio.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;
//pred[] stores the predecessor of each node
//count gives the number of nodes seen so far
//create the cost matrix
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];
//initialize pred[],distance[] and visited[]
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;
//nextnode gives the node at minimum distance
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i])
{
mindistance=distance[i];
nextnode=i;
}
//check if a better path exists through nextnode
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++;
}
 
//print the path and distance of each node
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);
}
}

Example 2: Dijkstra’s Algorithm code in C

#include<stdio.h>#include<conio.h>#define INFINITY 9999#define MAX 10 void dijikstra(int G[MAX][MAX], int n, int startnode); void main(){	int G[MAX][MAX], i, j, n, u;	clrscr();	printf("\nEnter the 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);	dijikstra(G,n,u);	getch();} void dijikstra(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 %d = %d", i, distance[i]);			printf("\nPath = %d", i);			j=i;			do			{				j=pred[j];				printf(" <-%d", j);			}			while(j!=startnode);		}}