Home » Data Structure

Shortest path between two nodes in graph using Djikstra algorithm



This article will tell you what is graph, nodes, shortest distance and how to find it by Djikstra algorithm?
Submitted by Manu Jemini, on January 06, 2018

Graph is a set of nodes or known number of vertices. When these vertices are paired together, we call it edges. An Edge is a line from one node to other. Every edge can have its cost or weight.

Shortest path Algorith

Image source: https://courses.cs.vt.edu/csonline/DataStructures/Lessons/Graphs/graph.gif

Node is a vertex in the graph at a position. The Line between two nodes is an edge. The Edge can have weight or cost associate with it.

Shortest distance is the distance between two nodes. For Example, to reach a city from another, can have multiple paths with different number of costs. A path with the minimum possible cost is the shortest distance.

Djikstra algorithm asks for the source and destination. The Algorithm finds the shortest distance from current node to the next node and then at the next node look for the cheapest path for the next node.

Shortest path Algorith

Image source https://i.stack.imgur.com/tyTz7.pngsrc

Program:

#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 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()*/

void 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()*/

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)
            return 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()*/

Output

Shortest path alog output





Quick links:
C FAQ(s) C Advance programs C/C++ Tips & Tricks Puzzles JavaScript CSS Python Linux Commands PHP Android Articles More...

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.




Comments and Discussions





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com (2015-2018), Some rights reserved.