Dijkstra et gestion de chemin(s) inexistant(s)
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:
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:
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:
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:
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
