Dijkstra's Shortest Path Algorithm is the popular algorithm for finding shortest/optimal path in compute science due to its widespread application in different branches- computer networks, distributed systems, signal processing etc.
I've implemented the algorithm for finding the minimum distance between any two nodes:
I've implemented the algorithm for finding the minimum distance between any two nodes:
///......................................SHORTEST PATH ALGORITHM << Dijkstra Algorithm >>......................
#include<stdio.h>
#include<conio.h>
#define MAX_NODES 10
#define INFINITY 1000
#define MEMBER 1
#define NON_MEMBER 0
struct arc{
int adj;
int weight;
};
int main(){
int i,j,k,weight[MAX_NODES][MAX_NODES],num_nodes,source,dest,precede[MAX_NODES];
int distance[MAX_NODES],permanent_nodes_set[MAX_NODES];
int current,current_distance,n;
int smalldist,newdist;
char s,d,node;
printf("\n\t\t................................................................................\n");
printf("\t\t\t\tSHORTEST PATH ALGORITHM << Dijkstra Algorithm >>");
printf("\n\t\t................................................................................\n");
printf("\n\n\t\t\tAssign 1000 as INFINITY for non-adjacent nodes !!\n\n");
printf("\nEnter the number of nodes in the GRAPH :");
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
printf("\nEnter weight for arc[%c][%c] :",65+i,65+j);
scanf("%d",&weight[i][j]);
weight[j][i] =weight[i][j];
weight[i][i] =INFINITY;
}
printf("\nEnter the source _node :");scanf(" %c",&s);
source =(int)(s-97);
printf("\nEnter the destination_node :");scanf(" %c",&d);
dest = (int)(d-97);
printf("\n\t\t\tThe shortest path is :>>\n\n\t\t\t");
for(i=0;i<n;i++)
{
permanent_nodes_set[i] =NON_MEMBER;
distance[i] =INFINITY;
}
permanent_nodes_set[source]=MEMBER;
distance[source]=0;
current=source;
while(current!=dest)
{
smalldist =INFINITY;
current_distance =distance[current];
for(i=0;i<n;i++)
if(permanent_nodes_set[i] ==NON_MEMBER)
{
newdist =current_distance+weight[current][i];
if(newdist<distance[i])
{
distance[i]=newdist;
precede[i]=current;
if(node!=(65+current))
printf(" %c ->",65+current);
node =65+current;
}
if(distance[i]<smalldist)
{
smalldist =distance[i];
k =i;
}
}
current =k;
permanent_nodes_set[current] =MEMBER;
}
printf(" %c ->",65+dest);
printf("\n\n\t\t\tThe shortest distance = %d\n",distance[dest]);
getch();
return 0;
}