add alternative approach from 2013-01
[synclust.git] / src / sources / dijkstra.c
... / ...
CommitLineData
1#include "sources/dijkstra.h"
2#include <stdlib.h>
3#include "sources/utils/boolean.h"
4#include <math.h>
5
6// Dijkstra from index start : return vector of distances to every other vertex
7// TODO: use a good priority queue, and pass NI instead of pDistsIn (+ linear preprocessing)
8double* dijkstra_core(double* pDistsIn, int start, int n) {
9
10 // initalisations
11 double* pDistsOut = (double*)malloc(n*sizeof(double));
12 bool* visited = (bool*)malloc(n*sizeof(bool));
13 for (int i=0; i<n; i++) {
14 pDistsOut[i] = INFINITY;
15 visited[i] = S_FALSE; // nothing seen so far
16 }
17 pDistsOut[start] = 0.0; // we are at distance 0 from self
18
19 while (S_TRUE)
20 {
21 double minGeodDist = INFINITY;
22
23 // n1 <-- node in "unseen" with smallest geodesic distance
24 // NOTE: on first loop, n1 == start
25 int n1 = 0;
26 for (int i=0; i<n; i++)
27 {
28 if (!visited[i] && pDistsOut[i] < minGeodDist)
29 {
30 n1 = i;
31 minGeodDist = pDistsOut[i];
32 }
33 }
34
35 if (minGeodDist == INFINITY)
36 break; // all is explored
37
38 visited[n1] = S_TRUE; // n1 is expanded
39
40 // For n2 running through neighbors of n1
41 for (int n2 = 0; n2<n; n2++)
42 {
43 int ind_n12 = n1*n+n2; // or n1+n*n2 (symmetry)
44 if (!isnan(pDistsIn[ind_n12]))
45 {
46 // check if we'd better go through n1 (on the way from start to n2)
47 if (pDistsOut[n2] > pDistsOut[n1] + pDistsIn[ind_n12])
48 pDistsOut[n2] = pDistsOut[n1] + pDistsIn[ind_n12];
49 }
50 }
51 }
52 free(visited);
53
54 return pDistsOut;
55}