Djikstras : Single Source Shortest path

/*
* Status: Tested OK
* Title: Single source shortest path algorithm (Djikstra's algorithm)
* Category: Path Optimization
* Difficulty Level: Medium
* Name: Akshay Thakare
*/

#include <stdio.h>
#include <stdlib.h>

#define VISITED 9999
#define INFINITY 9999
#define NIL -1

int *visit;				//Stores the vertives which are not visited
int *d;					//Stores the minimum vertex distance from vertex selected
int *pie;				//Stores the direction of path
int **w;				//Weight matrix
int n;					//Stores the number of vertices present in the given graph
int i,j;				//Common iterator
int start;				//Starting vertex

void print_ans();

void memory_alloc()
{
	/*Dynamic memory allocation*/
	visit = malloc(n*sizeof(int));
	d = malloc(n*sizeof(int));
	pie = malloc(n*sizeof(int));
	w = malloc(n*sizeof(int *));
	for(i=0;i<n;i++)
		w[i] = malloc(n*sizeof(int));
}

void get()
{
	printf("\nEnter the number of vertice's of the graph = ");
	scanf("%d",&n);
	
	memory_alloc();					//To dynamically allocate memory to arrays

	printf("\nEnter start vertex (from 1 to %d)= ",n);
	scanf("%d",&start);
	start--;
	
	printf("\nEnter the weights of the edges below\n");
	for(i=0;i<n;i++)
	{
		for(j=i;j<n;j++)
		{
			if(i==j)
				w[i][j]=0;
			else
			{
				printf("\nEnter the weight of edge between %d to %d = ",i,j);
				scanf("%d",&w[i][j]);
				w[j][i]=w[i][j];
			}
		}
	}	
}

void initialize()
{
	for(i=0;i<n;i++)
	{
		visit[i] = i;
		d[i] = INFINITY;
		pie[i] = NIL;
	}	
}

int minimum()
{
	int i;
	int min=INFINITY;
	int temp_pos;
	
	for(i=0;i<n;i++)
	{
		if(d[i]<min&&visit[i]!=VISITED)
		{	
			min = d[i];
			temp_pos=i;
		}
	}
	return temp_pos;
}

void calc()
{
	int i,j;
	i=0;				//Iterator
	int u;				//Extract min
	
	d[start] = 0;
	while (i!=n)			//Till all the vertices are not visited
	{
		u = minimum();
		visit[u]=VISITED;
		
		for(j=0;j<n;j++)
		{
			if((w[u][j]!=0)&&(visit[j]!=VISITED))
			{
				if((d[u]+w[u][j])<d[j])
				{
					d[j]=w[u][j]+d[u];
					pie[j]=u;
				}
			}
		}
		i++;
	}
}

void print_ans()
{
	printf("\n");
	for(i=0;i<n;i++)
	{
		printf("%d ",pie[i]);
	}
}

int main()
{
	get();
	initialize();
	calc();
	print_ans();
	return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s