Posted By

stakisko on 11/09/11

Tagged

path

Versions (?)

Last Edited at 11/09/11 10:37pm

Statistics

Viewed 1004 times

Favorited by 0 user(s)

Related snippets

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.

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

Highlighted TextExpand

/*
 *
 *  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 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++)
		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;
}

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.