Hello,
I'm working on implementing Dijkstra's Algorithm in C, and have run into a glitch. I can't seem to tack down the source of the glitch, but whenever I give my program the 25 node matrix, the first 20 nodes all calculate properly, but the last 5 are defaulting to as if there was a direct path from source to them, when there isn't.
Here's the code:
Code:#include <stdio.h>#include <time.h> #define infinity 998 #define MAX 25 int prev[25]; void printPath(int index) { if (prev[index] > 0) { printPath(prev[index]); } if(prev[index] == 0 || prev[index] == -1) printf("1 "); printf("%d ", index+1); } void lowestCost(int nodes, int startN, int cost[MAX][MAX], int *distance) //Dijkstra's Algorithm Function { int i,j,count,k,flag[MAX],min; for(i=0;i<nodes;i++) { flag[i] = 0; distance[i] = cost[startN][i]; //fill in initial known distances from start node to neighbors. if(distance[i] != infinity) { prev[i] = startN; //set parent as the start node if distance is not infinity. } else { prev[i] = -1; //no path found yet, need to dig deeper. } } count = 0; while(count<=nodes) { min=100; for(j=0;j<nodes;j++) { if(distance[j]<min && !flag[j]) min=distance[j],k=j; } flag[k]=1; count++; for(j=0;j<nodes;j++) { if(((distance[k]+cost[k][j]<distance[j]) || distance[j] == infinity) && !flag[j]) //new route found, shorter distance calculated. { distance[j]=distance[k]+cost[k][j]; prev[j] = k; //update path } } } } int main( ) { int nodes, startN, i, j, cost[MAX][MAX], distance[MAX]; int t; t = clock(); nodes = 25; for(i=0; i< nodes; i++) { for(j=0; j<nodes; j++) { scanf("%d",&cost[i][j]); if(cost[i][j] == 0) cost[i][j] = infinity; } } for(i = 0; i < nodes; i++) prev[i] = -1; startN = 0; lowestCost(nodes, startN, cost, distance); int z; for(z = 1; z < nodes; z++) { printf(" %dc %fs Path to %d: ", t, ((float)t/10000), z+1); printPath(z); printf("\n"); } return 0; }
Here's the matrix:
The output I've been getting so far is the following:
Ignore the time calculations, those are still being worked on after getting the algorithm working 100%.1502c 0.150200s Path to 2: 1 2 1502c 0.150200s Path to 3: 1 12 3
1502c 0.150200s Path to 4: 1 2 4
1502c 0.150200s Path to 5: 1 2 4 5
1502c 0.150200s Path to 6: 1 2 4 5 6
1502c 0.150200s Path to 7: 1 2 4 5 6 7
1502c 0.150200s Path to 8: 1 2 4 5 8
1502c 0.150200s Path to 9: 1 2 4 5 8 9
1502c 0.150200s Path to 10: 1 2 4 5 10
1502c 0.150200s Path to 11: 1 2 4 5 10 11
1502c 0.150200s Path to 12: 1 12
1502c 0.150200s Path to 13: 1 2 4 5 10 13
1502c 0.150200s Path to 14: 1 2 4 5 10 14
1502c 0.150200s Path to 15: 1 2 4 5 10 13 15
1502c 0.150200s Path to 16: 1 12 16
1502c 0.150200s Path to 17: 1 12 17
1502c 0.150200s Path to 18: 1 2 4 5 10 13 18
1502c 0.150200s Path to 19: 1 12 19
1502c 0.150200s Path to 20: 1 12 20
1502c 0.150200s Path to 21: 1 2 4 5 10 13 15 21
1502c 0.150200s Path to 22: 1 12 22
1502c 0.150200s Path to 23: 1 12 23
1502c 0.150200s Path to 24: 1 12 24
1502c 0.150200s Path to 25: 1 12 25
Thank you for your time, and feedback.
--
Alex