/ Published in: C

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.
Expand |
Embed | Plain Text
/* * * Created on: Nov 4, 2011 * Author: stakisko * Email : konmpar at gmail com */ /* #include <stdio.h> #include <stdlib.h> typedef struct _node node; typedef struct _acne acne; /* * There are two structures. * 'Node' represent each node having childrens acnes represent each connected to him nodes. * 'Acne' represent each acne connecting two Nodes. */ struct _node { int distance; // distance from the first node struct _acne *children[100]; // going to nodes int edgeno; // how many nodes are connected to int name; }; struct _acne { int value; // distance between these edges int from; // acne connecting from int to; // to struct _node *edge; }; /* * for every node we are going in (the parameter) we search its connected childs nodes and * calculate their distances. then we are going in again( recursion ) in the node with the * minimum distance * * */ int traverse(struct _node *node){ if(node->edgeno<=0) return 0; int mindistance = node->children[0]->value; int minnode = 0; int i; for(i=0;i<node->edgeno; i++){ if(node->distance + node->children[i]->value < node->children[i]->edge->distance ){ node->children[i]->edge->distance = node->distance + node->children[i]->value; } if (mindistance > node->children[i]->edge->distance){ mindistance = node->children[i]->edge->distance; minnode = i; } printf("\tfrom %d to %d with distance %d\n", node->children[i]->from, node->children[i]->to, node->children[i]->edge->distance); } traverse(node->children[minnode]->edge); return 0; } // main function int main(int argc, char *argv[]){ FILE *ifp; int t, t1, t2; int nodesNo = 0; int edgesNo = 0; ifp = fopen("/home/kostas/Downloads/dijkstra1.dat", "r"); if (ifp == NULL) { fprintf(stderr, "Can't open input file dijkstra.dat!\n"); exit(1); } fscanf(ifp, "%d %d", &nodesNo, &edgesNo); struct _node nodes[nodesNo]; struct _acne acnes[edgesNo]; int i = 0; // count the acnes int previous = 0; int k = 0; // count childs for every node /* * 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 * */ while(fscanf(ifp, "%d %d %d", &t, &t1, &t2) == 3){ /* read from file */ /* * Then for every line we create a node and also * an acne to place the connected edges. * */ if(previous != t) k = 0; nodes[t].distance = 65000; // infinite nodes[t].name = t; acnes[i].from = t; acnes[i].to = t1; acnes[i].value = t2; acnes[i].edge = &nodes[t1]; nodes[t].children[k] = &acnes[i]; nodes[t].edgeno = k+1; i++; k++; previous = t; } // set firsts node's distance nodes[0].distance = 0; // set last node nodes[nodesNo-1].distance = 65000; nodes[nodesNo-1].edgeno = 0; nodes[nodesNo-1].name = nodesNo-1; int j; for(j=0; j< (sizeof(nodes)/sizeof(*nodes));j++) for(j=0; j< sizeof(acnes)/sizeof(*acnes);j++) traverse(&nodes[0]); for(j=0; j< (sizeof(nodes)/sizeof(*nodes));j++) return 0; }
You need to login to post a comment.