Djikstra algorithm using Graph | how to find out shortest path between 2 node

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

Djikstra algorithm using graph

Share This