Dijkstra\'s Shortest Path algorithm


/ Published in: C
Save to your folder(s)

Its Dijkstra's Shortest Path algorithm written in C. Reads from a file the nodes and the connected edges and implements Dijkstra's algorithm. I am uploading for your comments in my code. Thank you.

<p>Files content should be in the format:
n N
startNode endNode distance
startNode endNode distance
.
.
.
startNode endNode distance </p>

<p>where n is the total number of Nodes and N is the total number of Acnes.</p>


Copy this code and paste it in your HTML
  1. /*
  2.  *
  3.  * Created on: Nov 4, 2011
  4.  * Author: stakisko
  5.  * Email : konmpar at gmail com
  6.  */
  7. /*
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11.  
  12. typedef struct _node node;
  13. typedef struct _acne acne;
  14.  
  15. /*
  16.  * There are two structures.
  17.  * 'Node' represent each node having childrens acnes represent each connected to him nodes.
  18.  * 'Acne' represent each acne connecting two Nodes.
  19.  */
  20.  
  21. struct _node {
  22. int distance; // distance from the first node
  23. struct _acne *children[100]; // going to nodes
  24. int edgeno; // how many nodes are connected to
  25. int name;
  26. };
  27.  
  28. struct _acne {
  29. int value; // distance between these edges
  30. int from; // acne connecting from
  31. int to; // to
  32. struct _node *edge;
  33. };
  34.  
  35. /*
  36.  * for every node we are going in (the parameter) we search its connected childs nodes and
  37.  * calculate their distances. then we are going in again( recursion ) in the node with the
  38.  * minimum distance
  39.  *
  40.  * */
  41.  
  42. int traverse(struct _node *node){
  43.  
  44. if(node->edgeno<=0)
  45. return 0;
  46.  
  47. printf("start of node %d\n", node->name);
  48. printf("\tchildrens: %d\n", node->edgeno);
  49.  
  50. int mindistance = node->children[0]->value;
  51. int minnode = 0;
  52.  
  53. int i;
  54.  
  55. for(i=0;i<node->edgeno; i++){
  56.  
  57. if(node->distance + node->children[i]->value < node->children[i]->edge->distance ){
  58. node->children[i]->edge->distance = node->distance + node->children[i]->value;
  59. }
  60.  
  61. if (mindistance > node->children[i]->edge->distance){
  62. mindistance = node->children[i]->edge->distance;
  63. minnode = i;
  64. }
  65.  
  66. printf("\tfrom %d to %d with distance %d\n", node->children[i]->from, node->children[i]->to, node->children[i]->edge->distance);
  67.  
  68. }
  69.  
  70. printf("\tmin node %d\n", node->children[minnode]->to);
  71.  
  72. printf("end of node\n-----------------------\n");
  73.  
  74. traverse(node->children[minnode]->edge);
  75.  
  76. return 0;
  77. }
  78.  
  79. // main function
  80. int main(int argc, char *argv[]){
  81.  
  82. FILE *ifp;
  83.  
  84. int t, t1, t2;
  85. int nodesNo = 0;
  86. int edgesNo = 0;
  87.  
  88. ifp = fopen("/home/kostas/Downloads/dijkstra1.dat", "r");
  89.  
  90. if (ifp == NULL) {
  91. fprintf(stderr, "Can't open input file dijkstra.dat!\n");
  92. exit(1);
  93. }
  94.  
  95. fscanf(ifp, "%d %d", &nodesNo, &edgesNo);
  96.  
  97. struct _node nodes[nodesNo];
  98. struct _acne acnes[edgesNo];
  99. int i = 0; // count the acnes
  100. int previous = 0;
  101. int k = 0; // count childs for every node
  102.  
  103. /*
  104. * Files content should be in the format
  105. * n N
  106. * startNode endNode distance
  107. * startNode endNode distance
  108. * .
  109. * .
  110. * .
  111. * startNode endNode distance
  112. *
  113. * where n is the total number of Nodes and N is the total number of Acnes
  114. *
  115. */
  116. while(fscanf(ifp, "%d %d %d", &t, &t1, &t2) == 3){ /* read from file */
  117.  
  118. /*
  119. * Then for every line we create a node and also
  120. * an acne to place the connected edges.
  121. *
  122. */
  123. if(previous != t)
  124. k = 0;
  125.  
  126. nodes[t].distance = 65000; // infinite
  127. nodes[t].name = t;
  128.  
  129. acnes[i].from = t;
  130. acnes[i].to = t1;
  131. acnes[i].value = t2;
  132. acnes[i].edge = &nodes[t1];
  133.  
  134. nodes[t].children[k] = &acnes[i];
  135.  
  136. nodes[t].edgeno = k+1;
  137.  
  138. i++;
  139. k++;
  140. previous = t;
  141. }
  142.  
  143. // set firsts node's distance
  144. nodes[0].distance = 0;
  145.  
  146. // set last node
  147. nodes[nodesNo-1].distance = 65000;
  148. nodes[nodesNo-1].edgeno = 0;
  149. nodes[nodesNo-1].name = nodesNo-1;
  150.  
  151. int j;
  152. for(j=0; j< (sizeof(nodes)/sizeof(*nodes));j++)
  153. printf("node %d, distance %d, edgeno %d\n", nodes[j].name, nodes[j].distance, nodes[j].edgeno);
  154.  
  155. for(j=0; j< sizeof(acnes)/sizeof(*acnes);j++)
  156. printf("from %d, to %d, value %d\n", acnes[j].from, acnes[j].edge->name, acnes[j].value);
  157.  
  158. printf("\n-----------\n");
  159. traverse(&nodes[0]);
  160. printf("\n-----------\n");
  161.  
  162. for(j=0; j< (sizeof(nodes)/sizeof(*nodes));j++)
  163. printf("nnode %d, distance %d\n", nodes[j].name, nodes[j].distance);
  164.  
  165. return 0;
  166. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.