Untitled

 avatar
unknown
plain_text
a year ago
3.3 kB
3
Indexable
/* Program of shortest path between two node in graph using Djikstra algorithm */
#include<stdio.h>

#define MAX 10
#define TEMP 0
#define PERM 1
#define infinity 9999

struct node
{
	int predecessor;
	int dist; /minimum distance of node from source/
	int status;
};

int adj[MAX][MAX];
int n;
void main()
{
	int i,j;
	int source,dest;
	int path[MAX];
	int shortdist,count;

	create_graph();
	printf("The adjacency matrix is :\n");
	display();

	while(1)
	{
		printf("Enter source node(0 to quit) : ");
		scanf("%d",&source);
		printf("Enter destination node(0 to quit) : ");
		scanf("%d",&dest);

		if(source==0 || dest==0)
			exit(1);

		count = findpath(source,dest,path,&shortdist);
		if(shortdist!=0)
		{
			printf("Shortest distance is : %d\n", shortdist);
			printf("Shortest Path is : ");
			for(i=count;i>1;i--)
				printf("%d->",path[i]);
			printf("%d",path[i]);
			printf("\n");
		}
		else
			printf("There is no path from source to destination node\n");
	}/End of while/
}/End of main()/

create_graph()
{
	int i,max_edges,origin,destin,wt;

	printf("Enter number of vertices : ");
	scanf("%d",&n);
	max_edges=n*(n-1);

	for(i=1;i<=max_edges;i++)
	{
		printf("Enter edge %d(0 0 to quit) : ",i);
		scanf("%d %d",&origin,&destin);
		if((origin==0) && (destin==0))
			break;
		printf("Enter weight for this edge : ");
		scanf("%d",&wt);
		if( origin > n || destin > n || origin<=0 || destin<=0)
		{
			printf("Invalid edge!\n");
			i--;
		}
		else
			adj[origin][destin]=wt;
	}/End of for/
}/End of create_graph()/

display()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			printf("%3d",adj[i][j]);
		printf("\n");
	}

}/End of display()/

int findpath(int s,int d,int path[MAX],int *sdist)
{
	struct node state[MAX];
	int i,min,count=0,current,newdist,u,v;
	*sdist=0;
	/* Make all nodes temporary */
	for(i=1;i<=n;i++)
	{
		state[i].predecessor=0;
		state[i].dist = infinity;
		state[i].status = TEMP;
	}

	/Source node should be permanent/
	state[s].predecessor=0;
	state[s].dist = 0;
	state[s].status = PERM;

	/Starting from source node until destination is found/
	current=s;
	while(current!=d)
	{
		for(i=1;i<=n;i++)
		{
			/*Checks for adjacent temporary nodes */
			if ( adj[current][i] > 0 && state[i].status == TEMP )
			{
				newdist=state[current].dist + adj[current][i];
				/Checks for Relabeling/
				if( newdist < state[i].dist )
				{
					state[i].predecessor = current;
					state[i].dist = newdist;
				}
			}
		}/End of for/

		/Search for temporary node with minimum distand make it current node/
		min=infinity;
		current=0;
		for(i=1;i<=n;i++)
		{
			if(state[i].status == TEMP && state[i].dist < min)
			{
				min = state[i].dist;
				current=i;
			}
		}/End of for/

		if(current==0) /If Source or Sink node is isolated/
			return 0;
		state[current].status=PERM;
	}/End of while/

	/* Getting full path in array from destination to source	*/
	while( current!=0 )
	{
		count++;
		path[count]=current;
		current=state[current].predecessor;
	}

	/Getting distance from source to destination/
	for(i=count;i>1;i--)
	{
		u=path[i];
		v=path[i-1];
		*sdist+= adj[u][v];
	}
	return (count);
}/End of findpath()/
Editor is loading...
Leave a Comment