Revision: 53006
at November 10, 2011 08:47 by stakisko

Updated Code
```/*
*
*  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; // 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->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;

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.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);
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;
}```

Revision: 53005
at November 9, 2011 23:23 by stakisko

Updated Code
```/*
*
*  Created on: Nov 4, 2011
*      Author: kostas
*      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; // 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->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;

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.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);
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;
}```

Revision: 53004
at November 9, 2011 23:07 by stakisko

Updated Code
```/*
*  dijkstra.c
*
*  Created on: Nov 4, 2011
*      Author: kostas
*/
/*

#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; // 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->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;

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.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);
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;
}```

Revision: 53003
at November 9, 2011 22:59 by stakisko

Updated Code
```/*
*  dijkstra.c
*
*  Created on: Nov 4, 2011
*      Author: kostas
*/
/*

#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; // 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->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;

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.distance = 0;

// set last node
nodes[nodesNo-1].distance = 65000;
nodes[nodesNo-1].edgeno = 0;

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);
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;
}```

Revision: 53002
at November 9, 2011 22:38 by stakisko

Updated Code
```/*
*  dijkstra.c
*
*  Created on: Nov 4, 2011
*      Author: kostas
*/
/*

#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; // 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->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;

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.distance = 0;

// set last node
nodes[nodesNo-1].distance = 65000;
nodes[nodesNo-1].edgeno = 0;
nodes[nodesNo-1].name =  5;

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);
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;
}```

Revision: 53001
at November 9, 2011 22:37 by stakisko

Initial Code
```/*
*  dikstra.c
*
*  Created on: Nov 4, 2011
*      Author: kostas
*/
/*

#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; // 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->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;

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.distance = 0;

// set last node
nodes[nodesNo-1].distance = 65000;
nodes[nodesNo-1].edgeno = 0;
nodes[nodesNo-1].name =  5;

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);
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;
}```

Initial URL

Initial Description
```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>```

Initial Title
`Dijkstra\'s Shortest Path algorithm`

Initial Tags
`path`

Initial Language
`C`