Discussion :

[Grasshoper]

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

[JolyLoic]

Je n'ai pas le temps de lire tout ton algorithme, mais quelques pistes :

• Est-ce que tu fais tourner ton programme dans un mode debug, non optimisé ? Si c'est le cas, normalement tu devrais avoir des asserts dès que tu fais une mauvaise manip avec un de tes vectors (essaye éventuellement avec différents compilateurs)
• Tel que j'ai compris ton code, tu utilises un vector<vector<T>> pour représenter une matrice. C'est généralement une mauvaise idée en terme de performances, car la mémoire se trouve éclatée. Il vaut généralement mieux utiliser un seul vector, et indexer les éléments avec une formule comme ligne*nombreDeLignes + colonne, le tout encapsulé dans une petite classe qui va elle-même avoir des asserts qui vont bien pour valider les indices que tu lui passes en entrée...

[koala01]

Salut,

et indexer les éléments avec une formule comme ligne*nombreDeLignes + colonne

Heu, tu voulais sans doute écrir ligne * nombreDeColonne + colonne ou colonne*nombreDeLignes + ligne

Tant qu'à fournir une formule, autant qu'elle soit correcte

[JolyLoic]

En effet, mon clavier a fourché...

[CedricMocquillon]

Bonjour,
Ton approche n'est pas la plus optimale: tu vas calculer pour chaque couple de sommets du graphe (i,j) un plus court chemin avec l'algorithme de disjkstra pour déterminer la distance min entre i et j.
En fait tu recherche la matrice des plus courts chemin et dans ce cas, il existe un algorithme bien plus adapté: https://fr.wikipedia.org/wiki/Algori...Floyd-Warshall (complexité en O(n^3) avec n le nombre de sommets du graphe alors que ton approche est en O(n^2*(m+n*log(n)) )
Autre point je ne sais pas si tu es dans ce cas mais l'algorithme de dijkstra ne fonctionne que si les distances sont toutes positives (si tu as des distances négatives qui peuvent créer des cycles il faut que tu te tourne vers l'algorithme de bellman-ford)

[Grasshoper]

rebonjour à tous,
Et bien merci à tous pour vos réponses très détaillées et pleines de bon sens.
Pour répondre à quelques points:
Effectivement mon graphe n'a que des liens positifs et ce n'est pas une approche optimale (pour moi l'essentiel est quelle fonctionne dans un premier temps).
Je suis tout à fait d'accord pour réserver des blocs contigus de mémoire (c'est pourquoi je fonctionne habituellement en indexation linéaire comme vous le suggérez), pour le coup les vectors<vector<int>> sont la dans un premier temps. Il se trouve que maintenant l'algorithme fonctionne et que je me restreint à parcourir la partie triangulaire supérieure de la matrice d'adjacence, ce qui divise par 2 mon temps de calcul pour trouver une distance convenable, c'est déjà beaucoup mieux. L'approche en O(n^3) me plait bien je vais regarder ca dans un prochain temps, merci beaucoup!