probleme programme

Question

slt est ce que qlq un peut me dire pkoi le programme suivant ne marche pas: #include #include #define GRAPHSIZE 2048 #define INFINITY GRAPHSIZE*GRAPHSIZE #define MAX(a, b) ((a > b) ? (a) : (b)) int e; /* The number of nonzero edges in the graph */ int n; /* The number of nodes in the graph */ long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */ long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */ void printD() { int i; for (i = 1; i <= n; ++i) printf("%10d", i); printf(" "); for (i = 1; i <= n; ++i) { printf("%10ld", d[i]); } printf(" "); } void dijkstra(int s) { int i, k, mini; int visited[GRAPHSIZE]; for (i = 1; i <= n; ++i) { d[i] = INFINITY; visited[i] = 0; /* the i-th element has not yet been visited */ } d[s] = 0; for (k = 1; k <= n; ++k) { mini = -1; for (i = 1; i <= n; ++i) if (!visited[i] && ((mini == -1) || (d[i] < d[mini]))) mini = i; visited[mini] = 1; for (i = 1; i <= n; ++i) if (dist[mini][i]) if (d[mini] + dist[mini][i] < d[i]) d[i] = d[mini] + dist[mini][i]; } } main() { int i, j; int u, v, w; FILE *fin ; fin= fopen("dist11.txt", "r"); fscanf(fin, "%d", &e); for (i = 0; i < e; ++i) for (j = 0; j < e; ++j) dist[i][j] = 0; n = -1; for (i = 0; i < e; ++i) { fscanf(fin, "%d%d%d", &u, &v, &w); dist[u][v] = w; n = MAX(u, MAX(v, n)); } fclose(fin); dijkstra(1); printD(); getch(); } il m affiche le message suivant mon projet.exe a rencontré un probleme et doit se fermé qlq un a la solution? merci d avance

SAKingdom · Answer

for (k =  1; k <= n; ++k)
etc. etc. etc.

Un tableau commence  toujours à 0  et se termine donc à l'indice taille-1

for (k  = 0; k < n; ++k)

C++ (@++)<!--

The_Snail · Answer

Bonjour,

Je n'ai pas trop regarder ton code, mais ça m'étonnerais pas que ton problème viennent de ton tableau dist qui doit prendre trop de place dans la pile (j'ai déjà eu ce genre de problème, ça fait planter le programme à l'exécution).

La seule solution que je connaisse c'est d'allouer l'espace mémoire dynamiquement (dans le tas). Après je dis peut être des bêtises et si c'est le cas, on me corrigera . J'espère que ça pourra t'aider.

++

The_Snail · Answer

Rebonjour,

Bon apparament je t'ai dit des bêtises ne prend pas en compte mon message, je viens de test ce qu'a dit SAKingdom et ça marche très bien. Ca m'apprendra à lire le code en speed 

++

cs_maciass · Answer

a part les reponses betes y a il qlq un de vous capable de trouver la cause du probleme parce que la vous dites vraiment n importe koi

cs_jfrancois · Answer

Bonjour,

Il faudrait le contenu du fichier dist11.txt pour tester un peu ! (au moins un exemple minimal du contenu)

Jean-François

BruNews · Answer

for (i = 1; i <= n; ++i) {
  d[i] = INFINITY;
  ...
}

comme dit par SAK, tu écris hors du tableau.
Commence par corriger les indexations erronées et tu verras ensuite de quel coté se trouvaient les bêtises.

ciao...
BruNews, MVP VC++

The_Snail · Answer

Salut,

Un conseille, lorsque tu ouvres un fichier pense à regarder si l'ouverture s'est bien passée.
Pour ton cas :

if(fin == NULL)
{
    printf("Erreur de lors de l'ouverture du fichier");
    exit(1);
}

Sans se test, si fopen n'arrive pas à ouvrir le fichier pour une raison ou une autre, ton programme plantera.

cs_jfrancois · Answer

1) Il y a aussi l'initilisation de la matrice qui est faux :

for (i=0 ; i<e ; ++i)
   for (j=0 ; j<e ; ++j)
      dist[i][j] = 0;

e = nombre d'arcs décrits dans le fichier. C'est sur GRAPHSIZE qu'il faut tourner en i et en j pour initialiser dist, pas sur e qui peut valoir jusqu'à (GRAPHSIZE * GRAPHSIZE) : Dans un graphe de 2048 sommets (GRAPHSIZE), où tous les sommets sont reliés entre eux, on a 4194304 arcs (e) listés dans le fichier !

for (i=0 ; i<GRAPHSIZE ; ++i)
   for (j=0 ; j<GRAPHSIZE ; ++j)
      dist[i][j] = 0;

2) Il y a aussi le fait que la numérotation des sommets commence à 0 dans le parcours des boucles comme dans l'utilisation des indices des tables ! J'imagine que dans le fichier, les sommets sont numérotés par rapport à 1 et quand on appel dijkstra(1) c'est pour chercher les distances les plus courtes par rapport au premier sommet et non par rapport au deuxième !

3) Dans l'algorithme de Dijkstra, les arcs non renseignés (sommets non connectés) sont sensés être à INFINI, pas à 0. Dans ce programme le 0 est pris en compte comme l'INFINI dans l'algorithme, donc, a priori, c'est pas génant. Seulement voilà ! Un arc à 0 est une valeur tout à fait possible dans un graphe !!!

Jean-François

cs_maciass · Answer

en fait ce n est pas ce projet n est pas le mien mais d un ami qui m a demandé de le poster ici pour trouver une solution mais il a decidé de le laisser tomber


merci pour vos reponses

cs_maciass · Answer

dsl pour le (ce n est pas) qui n a pas de sens
j etai entrain de penser a autr chose

Probleme programme

10 réponses

Votre réponse

Discussions similaires