I made a quick & dirty implementation of the dijksta algorithm which is useful to find the shortest path between two nodes in a (weighted) graph
An example:
In this graph we have five nodes and the weight of each edge (e.g. distance to travel, time to get there, etc.)
The shortest path between 0 and 2 is the orange one with total cost of 6 (3+3)
Now the code:
First some variables
int nodes[5][5]; // distances in the graph as a adjacence matrix
int tmpnodes[5]; // tmp array
int distance[5]; // array for the found distances
int predecessor[5]; // array for the found predecessors
int numnodes = 5; // how many nodes are in the graph
Then we have to init some vars
void init_nodes() {
// set all edges to -1 for 'not connected'
int i,j;
for (i = 0; i < numnodes; i++) {
for (j = 0; j < numnodes; j++) {
nodes[i][j] = -1;
}
}
// set the values for the edges
// nodes[0][1] = 7 means the costs to travel from 0 to 1 is 7
// nodes[1][0] could also be another value
nodes[0][1] = 7;
nodes[0][4] = 3;
nodes[1][2] = 6;
nodes[1][3] = 4;
nodes[3][2] = 1;
nodes[3][4] = 2;
nodes[4][1] = 2;
nodes[4][2] = 3;
// set the distance between all nodes to 999
// if you have costs over 999 set a higher value
for (i = 0; i < numnodes; i++) {
distance[i] = 999;
}
// set the distance to the start node to 0
// if 0 is not your start node chance to distance[startnode]
distance[0] = 0;
}
now the algorihm:
int dijkstra(int src, int tgt) {
// init variables
int i = 0;
for (i = 0; i < numnodes; i++) {
tmpnodes[i] = 1;
}
var minNode;
int runDijkstra = 1;
while (runDijkstra == 1) {
// find the node with the minimal distance from the actual node
minNode = tgt;
for (i = 0; i < numnodes; i++) {
if ((distance[i] < distance[minNode]) && (tmpnodes[i] == 1)) {
minNode = i;
}
}
tmpnodes[minNode] = 0;
if (minNode == tgt) {
break;
}
// relax the edges
for (i = 0; i < numnodes; i++) {
predecessor[i] = i;
if (nodes[minNode][i] != -1) {
var newlen = nodes[minNode][i] + distance[minNode];
if (newlen < distance[i]) {
distance[i] = newlen;
predecessor[i] = minNode;
}
}
}
// check if there are nodes left to check
runDijkstra = 0;
for (i = 0; i < numnodes; i++) {
if (tmpnodes[i] == 1) {
runDijkstra = 1;
}
}
}
return distance[tgt];
}
the dijksta function returns the shortest path, in the predecessor array are the nodes you must follow to recreate the path (start with predecessor[target] ...)
remember it's only a quick & dirty implementation and there can be errors left and of course plenty of room for improvements
[edit]
maybe a mod can move this to the lite-c contrib forum, i posted it here as a reply to 'Space StarMap Stargates' but I think the contrib forum would be better
[/edit]
