src/sources/dijkstra.c

   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)
   8 double* 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 }