Find Shortest Path using Dijkstra's Algorithm
Code:
/* PROGRAM TO FIND SHORTEST PATH USING DIJKSTRA'S ALGORITHM THIS IS A STATICIMPLEMENTATION OF PROGRAM USING A TWO DIMENTIONAL WEIGHT MATRIX, BUT THISPROGRAM CANNOT SUPPORT A SENARIO WHERE NUMBER OF NODES OF A GRAPH MAYCHANGE DURING EXECUTION */#include<stdio.h>#include<conio.h>#define INFINITY 2000#define MAXNODES 4#define MEMBER 1#define NONMEMBER 0void shortpath(int weight[][MAXNODES], int , int ,int * ,int precede[]);int main(void){int i,j,s,t;int weight[MAXNODES][MAXNODES],precede[MAXNODES],pd;printf("\n Enter weight matrix ");for(i=0;i<MAXNODES;i++)for(j=0;j<MAXNODES;j++)scanf(" %d",&weight[i][j]);for(i=0;i<MAXNODES;i++){printf("\n");for(j=0;j<MAXNODES;j++)printf(" %d",weight[i][j]);}printf("\n Enter the starting node and the ending node: ");scanf(" %d %d",&s,&t);shortpath(weight,s,t,&pd,precede);printf("\n The shortest path from node %d to %d is : %d",s,t,pd);return(0);}void shortpath(int weight[][MAXNODES],int s, int t, int *pd, int precede[]){int distance[MAXNODES],perm[MAXNODES];int current,i,j,k,dc;int smalldist,newdist;/* initialization of perm and distance array */for(i=0;i<MAXNODES;i++){perm[i]=NONMEMBER;distance[i]=INFINITY;}perm[s] = MEMBER;distance[s] = 0;current = s;while(current != t){smalldist=INFINITY;dc=distance[current];for(i=0;i<MAXNODES;i++)if(perm[i]==NONMEMBER){newdist = dc + weight[current][i];if(newdist < distance[i]){distance[i]=newdist;precede[i]=current;}if(distance[i] < smalldist){smalldist = distance[i];k=i;}} /* end of for if */current = k;perm[current]=MEMBER;} /* END WHILE */*pd=distance[t];} /* end of shortpath function *//* END OF PROGRAM */
- 14725 reads