#include <acknex.h>
#include <default.c>
int nodes[10][10]; // distances in the graph as a adjacence matrix
int tmpnodes[10]; // tmp array
int distance[10]; // array for the found distances
int predecessor[10]; // array for the found predecessors
int numnodes = 10; // how many nodes are in the graph
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] = 85;
nodes[0][2] = 217;
nodes[0][7] = 173;
nodes[1][4] = 80;
nodes[1][0] = 85;
nodes[2][0] = 217;
nodes[2][5] = 186;
nodes[2][6] = 103;
nodes[3][6] = 183;
nodes[4][1] = 80;
nodes[4][8] = 250;
nodes[5][2] = 186;
nodes[6][2] = 103;
nodes[6][3] = 183;
nodes[6][9] = 167;
nodes[7][0] = 173;
nodes[7][9] = 502;
nodes[8][4] = 250;
nodes[8][9] = 84;
nodes[9][9] = 84;
nodes[9][6] = 167;
nodes[9][7] = 502;
// 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;
}
/*****************************************************************************/
int dijkstra(int src, int tgt) {
// init variables
int i = 0;
for (i = 0; i < numnodes; i++) {
tmpnodes[i] = 1;
predecessor[i] = 0;
}
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];
}
void main()
{
STRING* sTemp = str_create("");
STRING* sTemp2 = str_create("");
int start = 0;
int ziel = 9;
init_nodes();
int dist = dijkstra(start, ziel);
str_cpy(sTemp,"distance:\t");
str_cat(sTemp, str_for_num(sTemp2,dist));
error(sTemp);
str_cpy(sTemp,"path:\t");
int tmp = ziel;
str_cat(sTemp, str_for_num(sTemp2,ziel));
int tmp2;
int vorgaenger;
// run through predecessors
while (tmp != start) {
vorgaenger = predecessor[tmp];
str_cat(sTemp, " <- ");
str_cat(sTemp, str_for_num(sTemp2,vorgaenger));
tmp = vorgaenger;
}
// sTemp now contains the reversed path
error(sTemp);
}