Bonsoir à toutes et à tous,

Je me résous enfin à poster, après combattu plusieurs soir de suite, l'algorithme de Dijkstra (algorithme du plus court chemin entre deux nœuds dans un graphe).
Je souhaite en effet pouvoir calculer cette distance dans un graphe pour un ensemble de nœuds, jusqu'à ce que je trouve deux nœuds séparés d'une certaine distance. J'utilise un algorithme mis à disposition, après avoir implémenté une solution matricielle en MATLAB qui fonctionne mais qui est trop lente.

La première étape est de charger la matrice d'adjacence du graphe (qui est indéxée linéairement) et de la convertir en vector<vector <int>> comme ceci:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
 vector<vector<int>> adjm(nrows, vector<int>(nrows));
//copy adjacency matrix 'A' to adjm:
for(int i = 0; i < nrows; i++)
    for(int j = 0; j < nrows; j++)
         adjm[i][j] = A[i + j*nrows];
jusque la OK, et après affichage de adjm[][] ca semble bien se passer. hourra.

Ensuite je parcours un tableau (indexé linéairement) contenant l'index des nœuds permutés de facon aléatoire et pour chaque couple de nœud je calcule la distance minimale existante (ou pas si les nœuds ne sont pas connectés entre eux, possible dans le cas de 2 graphes disjoints):

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 for(i=0; i < nrows; i++) {
        //for earch values of 'R', compute the distance with other nodes in 'R':
        //search for distance 'distance' in other nodes using dijkstra's algorithm:
        for(j=0; j < nrows; j++) {
            if(j != i) {
                const int cur_dis = dijk(rand_idx[i], rand_idx[j], adjm);
 
                //if distance is >= requested distance, then proceed:
                if(cur_dis >= distance) {
                    //assign outputs and returns:
                    plhs[0] = mxCreateDoubleScalar(rand_idx[i]); //in
                    plhs[1] = mxCreateDoubleScalar(rand_idx[j]); //out
                    plhs[2] = mxCreateDoubleScalar(cur_dis); //fdistance
                    return;
                }
            }
        }
    }
en utilisant la fonction suivante:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
using namespace std;
const int inf = 1 << 30;
 
//given adjacency matrix adj, finds shortest path from A to B
int dijk(const int A, const int B, const vector< vector<int> > adj) {
  int n = adj.size();
  vector<int> dist(n);
  vector<bool> vis(n);
 
  for(int i = 0; i < n; ++i) {
    dist[i] = inf;
  }
  dist[A] = 0;
 
  for(int i = 0; i < n; ++i) {
    int cur = -1;
    for(int j = 0; j < n; ++j) {
      if (vis[j]) continue;
      if (cur == -1 || dist[j] < dist[cur]) {
        cur = j;
      }
    }
 
    vis[cur] = true;
    for(int j = 0; j < n; ++j) {
      int path = dist[cur] + adj[cur][j];
      mexPrintf("dist[%d]=%d + adj[%d][%d]=%d, path=%d < dist[j]=%d?\n", cur, dist[cur], cur, j, adj[cur][j], path, dist[j]);
      if (path < dist[j]) {
        dist[j] = path;
      }
    }
  }
 
  return dist[B];
}
problème, j'obtiens des sorties étranges du type (en utilisant l'affichage mexPrintf(...) dans la fonction):
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
dist[4]=0 + adj[4][0]=0, path=0 < dist[j]=1073741824?
dist[4]=0 + adj[4][1]=0, path=0 < dist[j]=1073741824?
dist[4]=0 + adj[4][2]=0, path=0 < dist[j]=1073741824?
dist[4]=0 + adj[4][3]=1, path=1 < dist[j]=1073741824?
dist[4]=0 + adj[4][4]=0, path=0 < dist[j]=0?
dist[4]=0 + adj[4][5]=0, path=0 < dist[j]=1073741824?
Et je ne trouve jamais (jamais!) de chemin de longueur voulue, alors qu'ils existent bien (vérifié par ailleurs!).
Cette valeur 1073741824 me fait penser à une erreur de type ou d'initialisation hasardeuse, mais je ne trouve pas. J'ai bien essayé "vector<int> dist(n, 0);" sans succès supplémentaire.

Merci à l'âme charitable qui voudra bien m'éclairer.

Bien à vous