(C) Dijkstra’s Shortest Path algorithm

By SnipBot | Published: November 9, 2011

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.

Files content should be in the format:
n N
startNode endNode distance
startNode endNode distance
.
.
.
startNode endNode distance

where n is the total number of Nodes and N is the total number of Acnes.

  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. }
This entry was posted in C and tagged , , , , , , , . Bookmark the permalink. Trackbacks are closed, but you can post a comment.

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Why ask?