Dijkstra_shortest_path_algorithm.c

//Uses a Priority Queue
//Extract-min operation on min-heap data structure - theta(log v)
//Negative Weights not allowed

#include<stdio.h>
#include<conio.h>
#define MAX 100

int G[MAX][MAX],pred[MAX],distance[MAX];       //Adjacency matrix  , Predecessor of the node , distance from source distance[source]=0 

int heap_size;

void dijkstra(int G[MAX][MAX],int,int);
void initialise_single_source(int G[MAX][MAX],int,int);
void relax(int,int);
int check(int*,int,int);


void build_min_heap(int*);
void min_heapify(int*,int);
int extract_min(int*);
int left(int);
int right(int);
void swap(int*,int,int);



int main()
{
	int n,i,j,s;
	printf("Enter number of vertices");
	scanf("%d",&n);
	heap_size=n;
	printf("\nEnter adjacency matrix");
	for (i=0;i<n;i++)
		for (j=0;j<n;j++)
			scanf("%d",&G[i][j]);
	printf("\nEnter starting node");
	scanf("%d",&s);
	dijkstra(G,s,n);
	return 0;
}

int check(int *visited,int node,int n)        //To check if node visited
{
	int i;
	for (i=0;i<n;i++)
	{
		if (visited[i]==node)
			return 1;
	}
	return 0;
}

void dijkstra (int G[MAX][MAX],int s,int n)
{
	int visited[n],queue[heap_size];
	int i=0,j;
	int min,index;
	index=0;
	int count=n;   
	for (i=0;i<n;i++)
		visited[i]=-1;
	for (i=0;i<heap_size;i++)
		queue[i]=i;
	initialise_single_source(G,s,n);
	build_min_heap(queue);
	while (count>1)       //Loop will run until queue is empty
	{
		min=extract_min(queue);
		visited[index]=min;
		for (i=0;i<n;i++)
		{
			if (G[min][i]!=0 && !(check(visited,i,n)))
			{
				relax(min,i);
			}	
		}
		index++;
		count--;
	}	
	
	//Print Distance and Path
	
	for (i=0;i<n;i++)
	{
		if (i!=s)
		{
			printf("\nDistance from %d = %d",i,distance);
			printf("\nPath= %d",i);
			j=i;
			do 
			{
				j=pred[j];
				printf("<-%d",pred[j]);
			}while(j!=s);
		}
	}
}

void initialise_single_source(int G[MAX][MAX],int s,int n)
{
	int i;
	for (i=0;i<n;i++)
	{
		distance[i]=65535;
		pred[i]=-1;
	}	
	distance[s]=0;
}

void relax(int min,int adj)
{
	if (distance[adj]>distance[min]+G[min][adj])
	{
		distance[adj]=distance[min]+G[min][adj];
		pred[adj]=min;
	}
}

void build_min_heap(int *queue)    //Min Heap 
{
	int i;
	for (i=(heap_size-2)/2 ; i>=0 ; i--)
	{
		min_heapify(queue,i);
	}
}



void min_heapify(int *queue,int node)    //Min Heap
{
		int l,r,smallest;
		l=left(node);
		r=right(node);
		if (l<heap_size && distance[queue[node]]>distance[queue[l]])
			smallest=l;
		else smallest=node;
		if (l<heap_size && distance[queue[r]]<distance[smallest])
			smallest=r;
		if (smallest!=node)
		{	
			swap(queue,smallest,node);
			min_heapify(queue,smallest);
		}	
}

int left (int node)      //Min heap
{
	return node*2+1;
}
int right (int node)   //Min heap
{
	return node*2+2;
}

void swap(int *queue,int smallest,int node)   //Min Heap
{
	int temp;
	temp=queue[node];
	queue[node]=smallest;
	queue[smallest]=node;
}

int extract_min(int *queue)          //Min heap
{
	int min;
	if (heap_size<0)
		printf("\nUnderflow");
	min=queue[0];
	queue[0]=queue[heap_size-1];
	heap_size=heap_size-1;
	min_heapify(queue,0,heap_size);
	return min;
}