## Posted By

stakisko on 11/09/11

# Dijkstra's Shortest Path algorithm

/ 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.

`/* * *  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; 	printf("start of node %d\n", node->name);	printf("\tchildrens: %d\n", node->edgeno); 	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); 	} 	printf("\tmin node %d\n", node->children[minnode]->to); 	printf("end of node\n-----------------------\n"); 	traverse(node->children[minnode]->edge); 	return 0;} // main functionint 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++)		printf("node %d, distance %d, edgeno %d\n", nodes[j].name, nodes[j].distance, nodes[j].edgeno); 	for(j=0; j< sizeof(acnes)/sizeof(*acnes);j++)		printf("from %d, to %d, value %d\n", acnes[j].from, acnes[j].edge->name, acnes[j].value); 	printf("\n-----------\n");	traverse(&nodes[0]);	printf("\n-----------\n"); 	for(j=0; j< (sizeof(nodes)/sizeof(*nodes));j++)		printf("nnode %d, distance %d\n", nodes[j].name, nodes[j].distance); 	return 0;}`