Dijkstra : Parametre modifie de sa propre initiative!?

Version imprimable

Bonjour a tous,
Il m'est demande pour ce soir de programmer le code de Dijkstra (parcourir un graphe d'un noeud a un autre en passant par le chemin le plus court) et d'afficher le tableau des chiffres.

Voici mon code :

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "graph.h"
 
void dijkstra_function (graphe g, unsigned int noeud_depart, unsigned int noeud_arrivee) //, unsigned int a, unsigned int b, unsigned int c, int** chemins, int* indices, int* sommets, int* marque)
{
	//On va d'abord creer toutes les variables locales dont on aura besoin
	int* marque = (int*)malloc(g->nbsommets*sizeof(int));
	unsigned int chiffres[g->nbsommets][g->nbsommets];
	unsigned int ligne=0;
	unsigned int colonne=0;
	unsigned int noeud_courant=0;
	unsigned int plupti_j=0;
	unsigned int i,j;
	unsigned int iteration=0;
	//Fin des variables locales
 
	//Conditions initiales pour que tout aille bien
	printf("g->nbsommets vaut: %d\n", g->nbsommets);
	if (noeud_depart<0 || noeud_depart>(g->nbsommets) || noeud_arrivee<0 || noeud_arrivee>(g->nbsommets))
	{
		printf("Erreur de parametres d'entree. Verifiez que les noeuds choisis sont bien entre 0 et le nombre de sommets du graphe.\n");
		exit;
	}
	if (&g==NULL || (g->nbsommets)<2)
	{
		printf("Le graphe entre en parametre est nul ou ne contient pas assez de noeuds pour qu'il vaille le coup de lancer l'algorithme.\n");
		exit;
	}
	//Fin des conditions initiales
 
	for (i=0; i<(g->nbsommets);i++)
	{
		marque[i]=0;
		for (j=0; j<(g->nbsommets); j++)
		{
			chiffres[i][j]=0;
		}
	}
 
	//Remplissage de la premiere ligne
	printf("g->nbsommets vaut: %d\n", g->nbsommets);	
	for (colonne=0; colonne<(g->nbsommets); colonne++)
	{
		if (colonne != noeud_depart)
		{
			chiffres[0][colonne]=INT_MAX;
		}
		else
		{
			chiffres[0][colonne]=0;
			marque[colonne]=1;
			noeud_courant=noeud_depart;
		}
	}
 
	while (marque[noeud_arrivee]!=1)
	{
			for (i=0; i<(g->nbsommets); i++)
			{
				printf("marques: %d ",marque[i]);
			}
			printf("\n");
			printf("Je suis a l'iteration %d\n", iteration);
			if (ligne+1>=(g->nbsommets))
			{
				printf("Attention, vous avez explose le tableau de chiffres par en bas!\n");
			}
 
			//Je parcours la ligne en dessous de la ligne courante
			for (colonne=0; colonne<(g->nbsommets); colonne++)
			{
				if (marque[colonne]==1 || g->adj[noeud_courant][colonne]==0 || chiffres[ligne][noeud_courant]+(g->adj[noeud_courant][colonne])>=chiffres[ligne][colonne])
				{
					chiffres[ligne+1][colonne]=chiffres[ligne][colonne];
				}
				else
				{
					chiffres[ligne+1][colonne]=chiffres[ligne][noeud_courant]+(g->adj[noeud_courant][colonne]);
				}
			}
 
			//Je localise le noeud le plus proche
			i=0;
			while(marque[i]==1 || chiffres[ligne+1][i]==INT_MAX)
			{
				i++;
			}
			j=chiffres[ligne+1][i];
			for (i=0; i<(g->nbsommets); i++)
			{
				if(chiffres[ligne+1][i]<j && marque[i]!=1);
				{
					noeud_courant=i;
				}
			}
			marque[noeud_courant]=1;
			for (i=0; i<(g->nbsommets); i++)
			{
				for (j=0; j<(g->nbsommets); j++)
				{
					printf("%d ",chiffres[i][j]);
				}
				printf("\n");
			}
			ligne++;
			iteration++;
	 }
}

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <stdlib.h>
//#include "dijkstra.c"
#include "graph.h"
 
int main()
{
	graphe g, g2, g3 ;
 
	g = creer_graphe(5) ;
 
	ajouter_arete(g,0,1,7) ;
	ajouter_arete(g,0,4,8) ;
	ajouter_arete(g,0,2,2) ;
	ajouter_arete(g,1,2,6) ;
	ajouter_arete(g,1,3,3) ;
	ajouter_arete(g,2,4,5) ;
 
	g2 = creer_graphe(7) ;
 
	ajouter_arete(g2,0,1,5) ;
	ajouter_arete(g2,0,6,8) ;
	ajouter_arete(g2,1,2,2) ;
	ajouter_arete(g2,1,5,4) ;
	ajouter_arete(g2,1,3,6) ;
	ajouter_arete(g2,2,5,3) ;
	ajouter_arete(g2,2,3,1) ;
	ajouter_arete(g2,2,4,2) ;
	ajouter_arete(g2,3,4,3) ;
	ajouter_arete(g2,3,6,7) ;
	ajouter_arete(g2,2,4,2) ;
 
	g3 = creer_graphe(6);
 
	ajouter_arete(g3,0,1,3) ;
	ajouter_arete(g3,0,2,1) ;
	ajouter_arete(g3,1,2,1) ;
	ajouter_arete(g3,1,3,3) ;
	ajouter_arete(g3,2,3,3) ;
	ajouter_arete(g3,2,4,5) ;
	ajouter_arete(g3,3,4,1) ;
	ajouter_arete(g3,3,5,3) ;
	ajouter_arete(g3,4,5,1) ;
 
	/*afficher_graphe(g) ;
	printf("estConnexe de g donne: %d\n", est_connexe(g));
	afficher_graphe(g2) ;
	printf("estConnexe de g2 donne: %d\n", est_connexe(g2));
 
	printf("Le sommet %d a pour degre : %d\n", 2, degre_sommet(g, 2)) ;
	lister_voisins(g, 2) ;*/
	afficher_graphe(g3);
	dijkstra_function(g3,0,6);
   return 0;
}

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#ifndef __GRAPH__
#define __GRAPH__
 
/* 
	Gestion de graphes non orientés, pondérés 
*/
 
 
/* 
	Structure représentant un graphe sous forme matricielle 
	Inclus la matrice d'adjacence et le nombre de sommets
	Les poids sur les sommets sont de type entiers
*/
struct s_graph
{
	unsigned int nbsommets ; //Nombre de sommets, ou taille
	int **adj ; //Matrice d'adjacence, remplie de 0 ou la longueur du chemin
} ;
 
typedef struct s_graph *graphe ;
 
 
 
/*
	Allouer un graphe de taille n
*/
graphe creer_graphe(unsigned int ) ;
 
 
 
/*
	Ajouter une arête
*/
void ajouter_arete(graphe , unsigned int , unsigned int, unsigned int ) ;
 
 
/*
	Afficher un graphe 
*/
void afficher_graphe(graphe ) ;
 
/*
	Retourner le degré d'un sommet (Nombre d'arretes incidentes)
*/
int degre_sommet(graphe , unsigned int) ;
 
/*
	Lister les voisins d'un sommet
*/
void lister_voisins(graphe , unsigned int) ;
 
#endif

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include "graph.h"
#include "stdlib.h"
#include "stdio.h"
 
 
graphe creer_graphe(unsigned int n)
{
	unsigned int som ;
 
	/* Allocation de la structure graphe */
	graphe g = (graphe)malloc(sizeof(struct s_graph)) ;	
	if (!g) 
	{
		perror ("Echec allocation") ;
		exit(1) ;
	}
	g->nbsommets = n ;
 
	/* Allocation de la dimension 1 */
	g->adj = (int **)malloc(sizeof(int*) * n) ; 	
	if (!(g->adj)) 
	{
		perror ("Echec allocation") ;
		exit(1) ;
	}
 
	/* Allocation des n elements de la dimension 2 */
	for(som=0 ; som<n ; som++)
	{
		unsigned int som2 ;
		g->adj[som] = (int *)malloc(sizeof(int) * n) ; 	
		if (!(g->adj[som])) 
		{
			perror ("Echec allocation") ;
			exit(1) ;
		}
		/* Valeur par défaut : 0, pas d'arête */
		for(som2=0 ; som2<n ; som2++)
		{
			g->adj[som][som2] = 0 ;
		}
	}
 
	return g ;
}
 
void ajouter_arete(graphe g, unsigned int a, unsigned int b, unsigned int poids) 
{
	/* Vérifier que les numéros de sommets sont bons */
	if ( (a < 0) || (b < 0) || (a >= g->nbsommets) || (b >= g->nbsommets) || (a == b) )
	{
		fprintf(stderr, "Ajout de l'arete impossible\n") ;
		exit(1) ;
	}
	else
	{
		g->adj[a][b] = poids ;
		g->adj[b][a] = poids ;
	}
}
 
 
void afficher_graphe(graphe g) 
{
	unsigned int x,y ;
 
	printf("Affichage du graphe :\n");
	for (x=0 ; x<g->nbsommets ; x++)
	{
		for (y=0 ; y<g->nbsommets ; y++)
		{
			printf("%d ",g->adj[x][y]) ;
		}
		printf("\n");
	}
}
 
 
int degre_sommet(graphe g, unsigned int som) 
{
	/* Vérifier que le numéro du sommet est bon */
	if ( (som < 0) || (som >= g->nbsommets) )
	{
		fprintf(stderr, "degre du sommet impossible\n") ;
		exit(1) ;
	}
	else
	{
		unsigned int temp = 0;
		unsigned int y ;
		for (y=0 ; y<g->nbsommets ; y++)
		{
			if (g->adj[som][y] != 0)
				temp += 1 ;
		}	
		return temp ;
	}
}
 
 
void lister_voisins(graphe g, unsigned int som) 
{
	/* Vérifier que le numéro du sommet est bon */
	if ( (som < 0) || (som >= g->nbsommets) )
	{
		fprintf(stderr, "degre du sommet impossible\n") ;
		exit(1) ;
	}
	else
	{	
		unsigned int y ;
		printf("Voisins du sommet %d:\n", som);		
		for (y=0 ; y<g->nbsommets ; y++)
		{
			if (g->adj[som][y] != 0)
				printf("\t Sommet %d avec une arete de poids %d\n", y, g->adj[som][y]) ;
		}			
	}
}
 
void cc (int s, graphe g, int* marque) //ComposanteConnexe marque tous les sommets accessibles a partir d'un sommet quelconque.
													//Si tous les sommets sont marques, alors le graphe est connexe.
{
	int i;
	marque[s]=1;
 
	for (i=0; i<(g->nbsommets); i++)
	{
		if ((marque[i]==0) && (g->adj[s][i]!=0)) //Si on n'est pas passe par le sommet i en partant de s ET que s est relie a i, on recommence avec i
		{
			cc(i,g,marque);
		}	
	}
	//On sort de la boucle une fois que le noeud sur lequel on est est marque.
}
 
int est_connexe (graphe g) //Un graphe est connexe si tous les noeuds sont relies entre eux. Autrement dit, on peut acceder a n'importe
									//quel noeud du graphe a partir d'un noeud aleatoirement choisi dans celui-ci.
{
	int i;
	int* marque = (int*)malloc((g->nbsommets)*sizeof(int));
 
	for (i=0; i<(g->nbsommets); i++)
	{
		marque[i]=0;
	}
 
	cc(0,g,marque);
 
	while (marque[i]!=0 && i<(g->nbsommets))
	{
		i++;
	}
 
	if (i==(g->nbsommets))
	{
		printf("Le graphe est connexe.\n");
		return 1;
	}
	else
	{
		printf("Le graphe n'est pas connexe.\n");
		return 0;
	}	
}

Tous les fichiers precedents sont programmes par mon prof sauf le premier, celui qui contient Dijkstra. C'est donc sur celui-la qu'il faudra focaliser pour repondre a mes questions.

Mes problemes:

- Dans dijsktra, mon parametre noeud_depart se modifie tout seul et prend des valeurs demesurees. Cela fait plusieurs jours que j'essaie de comprendre pourquoi, rien a faire!

- Dans la portion de code :

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
			//Je localise le noeud le plus proche
			i=0;
			while(marque[i]==1 || chiffres[ligne+1][i]==INT_MAX)
			{
				i++;
			}
			j=chiffres[ligne+1][i];
			for (i=0; i<(g->nbsommets); i++)
			{
				if(chiffres[ligne+1][i]<j && marque[i]!=1);
				{
					noeud_courant=i;
				}
			}
			marque[noeud_courant]=1;
			for (i=0; i<(g->nbsommets); i++)
			{
				for (j=0; j<(g->nbsommets); j++)
				{
					printf("%d ",chiffres[i][j]);
				}
				printf("\n");
			}
			ligne++;
			iteration++;

C'est toujours le dernier noeud de la ligne qui est pris comme noeud courant, alors que je precise qu'il faut que ce soit le plus petit contenu de la ligne si le noeud n'est pas marque!
Resultat de la compilation:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
Affichage du graphe :
0 3 1 0 0 0 
3 0 1 3 0 0 
1 1 0 3 5 0 
0 3 3 0 1 3 
0 0 5 1 0 1 
0 0 0 3 1 0 
noeud_depart vaut: 0
g->nbsommets vaut: 6
g->nbsommets vaut: 6
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 0
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 1
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 3
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 4
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 5
Attention, vous avez explose le tableau de chiffres par en bas!
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
Segmentation fault
joe@ubuntu:~/ESILV/S5/Algo/TP3$ gcc -o dijkstra *.c *.h -g -lm
joe@ubuntu:~/ESILV/S5/Algo/TP3$ ./dijkstra
Affichage du graphe :
0 3 1 0 0 0 
3 0 1 3 0 0 
1 1 0 3 5 0 
0 3 3 0 1 3 
0 0 5 1 0 1 
0 0 0 3 1 0 
noeud_depart vaut: 0
g->nbsommets vaut: 6
g->nbsommets vaut: 6
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 0
Ici, ligne+1 vaut: 1
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 1
Ici, ligne+1 vaut: 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 2
Ici, ligne+1 vaut: 3
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 3
Ici, ligne+1 vaut: 4
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 4
Ici, ligne+1 vaut: 5
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 5
Attention, vous avez explose le tableau de chiffres par en bas!
Ici, ligne+1 vaut: 6
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
Segmentation fault
joe@ubuntu:~/ESILV/S5/Algo/TP3$ gcc -o dijkstra *.c *.h -g -lm
joe@ubuntu:~/ESILV/S5/Algo/TP3$ ./dijkstra
Affichage du graphe :
0 3 1 0 0 0 
3 0 1 3 0 0 
1 1 0 3 5 0 
0 3 3 0 1 3 
0 0 5 1 0 1 
0 0 0 3 1 0 
noeud_depart vaut: 0
g->nbsommets vaut: 6
g->nbsommets vaut: 6
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 0
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 1
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 3
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 4
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 5
Attention, vous avez explose le tableau de chiffres par en bas!
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
Segmentation fault
joe@ubuntu:~/ESILV/S5/Algo/TP3$ gcc -o dijkstra *.c *.h -g -lm
joe@ubuntu:~/ESILV/S5/Algo/TP3$ ./dijkstra
Affichage du graphe :
0 3 1 0 0 0 
3 0 1 3 0 0 
1 1 0 3 5 0 
0 3 3 0 1 3 
0 0 5 1 0 1 
0 0 0 3 1 0 
noeud_depart vaut: 0
g->nbsommets vaut: 6
g->nbsommets vaut: 6
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 0
noeud_depart= 0
noeud_courant= 5
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 1
noeud_depart= 0
noeud_courant= 5
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 2
noeud_depart= 0
noeud_courant= 5
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 3
noeud_depart= 0
noeud_courant= 5
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 4
noeud_depart= 0
noeud_courant= 5
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 1 
Je suis a l'iteration 5
Attention, vous avez explose le tableau de chiffres par en bas!
noeud_depart= 2147483647
noeud_courant= 5
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
Segmentation fault

Help! Merci d'avance.

J'avance, c'etait a cause d'un bete point-virgule apres mon if!
Bon maintenant j'ai:

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
			while(marque[i]==1 || chiffres[ligne+1][i]==INT_MAX)
			{
				i++;
				if (i>=(g->nbsommets))
				{
					printf("Attention, vous avez explose le tableau par la droite.\n");
				}
			}
			j=chiffres[ligne+1][i];
			for (i=0; i<(g->nbsommets); i++)
			{
				if(chiffres[ligne+1][i]<j && marque[i]!=1) //Il semblerait que cette condition ne soit pas respectee
				{
					noeud_courant=i;
				}
			}
			printf("J'ai pris comme noeud courant %d\n", noeud_courant);
			marque[noeud_courant]=1; //Il n'a pas l'air de le faire!
			for (i=0; i<(g->nbsommets); i++)
			{
				for (j=0; j<(g->nbsommets); j++)
				{
					printf("%d ",chiffres[i][j]);
				}
				printf("\n");
			}
			ligne++;
			iteration++;
	 }

Et bien que je lui dise de ne pas prendre de noeud deja marque comme potentiel noeud_courant, il le fait quand meme, donc comme il prend tout le temps le meme noeud_courant, il recopie la meme ligne et explose le tableau par en bas! Pourquoi il ne respecte pas mes conditions en rouge?

Compilation:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
Affichage du graphe :
0 3 1 0 0 0 
3 0 1 3 0 0 
1 1 0 3 5 0 
0 3 3 0 1 3 
0 0 5 1 0 1 
0 0 0 3 1 0 
g->nbsommets vaut: 6
g->nbsommets vaut: 6
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 0
Je suis un compilateur maboule, qui pense effectivement que 1 < 3 a la ligne 1
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 1
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 3
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 4
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 5
Attention, vous avez explose le tableau de chiffres par en bas!
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 6
Attention, vous avez explose le tableau de chiffres par en bas!
Segmentation fault
joe@ubuntu:~/ESILV/S5/Algo/TP3$ gcc -o dijkstra *.c *.h -g -lm
joe@ubuntu:~/ESILV/S5/Algo/TP3$ ./dijkstra
Affichage du graphe :
0 3 1 0 0 0 
3 0 1 3 0 0 
1 1 0 3 5 0 
0 3 3 0 1 3 
0 0 5 1 0 1 
0 0 0 3 1 0 
g->nbsommets vaut: 6
g->nbsommets vaut: 6
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 0
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 1
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 2
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 3
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 4
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 5
Attention, vous avez explose le tableau de chiffres par en bas!
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 6
Attention, vous avez explose le tableau de chiffres par en bas!
Segmentation fault
joe@ubuntu:~/ESILV/S5/Algo/TP3$ gcc -o dijkstra *.c *.h -g -lm
joe@ubuntu:~/ESILV/S5/Algo/TP3$ ./dijkstra
Affichage du graphe :
0 3 1 0 0 0 
3 0 1 3 0 0 
1 1 0 3 5 0 
0 3 3 0 1 3 
0 0 5 1 0 1 
0 0 0 3 1 0 
g->nbsommets vaut: 6
g->nbsommets vaut: 6
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 0
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 1
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 2
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 3
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 4
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 5
Attention, vous avez explose le tableau de chiffres par en bas!
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 6
Attention, vous avez explose le tableau de chiffres par en bas!
Segmentation fault

J'ai trouve aussi!
Il fallait mettre un <= et non un < dans cette portion de code (en rouge):

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
			while(marque[i]==1 || chiffres[ligne+1][i]==INT_MAX)
			{
				i++;
				if (i>=(g->nbsommets))
				{
					printf("Attention, vous avez explose le tableau par la droite.\n");
				}
			}
			j=chiffres[ligne+1][i];
			for (i=0; i<(g->nbsommets); i++)
			{
				if(chiffres[ligne+1][i]<=j && marque[i]!=1) //Il semblerait que cette condition ne soit pas respectee
				{
					noeud_courant=i;
				}
			}
			printf("J'ai pris comme noeud courant %d\n", noeud_courant);
			marque[noeud_courant]=1; //Il n'a pas l'air de le faire!
			for (i=0; i<(g->nbsommets); i++)
			{
				for (j=0; j<(g->nbsommets); j++)
				{
					printf("%d ",chiffres[i][j]);
				}
				printf("\n");
			}
			ligne++;
			iteration++;
	 }

Si ca peut rendre service aux autres... ^^
Mon algo marche!

Compilation:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
Affichage du graphe :
0 3 1 0 0 0 
3 0 1 3 0 0 
1 1 0 3 5 0 
0 3 3 0 1 3 
0 0 5 1 0 1 
0 0 0 3 1 0 
g->nbsommets vaut: 6
g->nbsommets vaut: 6
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 0
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 1
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 2
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 3
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 4
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 5
Attention, vous avez explose le tableau de chiffres par en bas!
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 6
Attention, vous avez explose le tableau de chiffres par en bas!
Segmentation fault
joe@ubuntu:~/ESILV/S5/Algo/TP3$ gcc -o dijkstra *.c *.h -g -lm
joe@ubuntu:~/ESILV/S5/Algo/TP3$ ./dijkstra
Affichage du graphe :
0 3 1 0 0 0 
3 0 1 3 0 0 
1 1 0 3 5 0 
0 3 3 0 1 3 
0 0 5 1 0 1 
0 0 0 3 1 0 
g->nbsommets vaut: 6
g->nbsommets vaut: 6
marques: 1 marques: 0 marques: 0 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 0
J'ai pris comme noeud courant 2
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 0 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 1
J'ai pris comme noeud courant 1
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 1 marques: 1 marques: 0 marques: 0 marques: 0 
Je suis a l'iteration 2
J'ai pris comme noeud courant 3
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 0 0 0 0 0 
0 0 0 0 0 0 
marques: 1 marques: 1 marques: 1 marques: 1 marques: 0 marques: 0 
Je suis a l'iteration 3
J'ai pris comme noeud courant 4
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 5 7 
0 0 0 0 0 0 
marques: 1 marques: 1 marques: 1 marques: 1 marques: 1 marques: 0 
Je suis a l'iteration 4
J'ai pris comme noeud courant 5
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 5 7 
0 2 1 4 5 6 
marques: 1 marques: 1 marques: 1 marques: 1 marques: 1 marques: 1 
Je suis a l'iteration 5
Attention, vous avez explose le tableau de chiffres par en bas!
Attention, vous avez explose le tableau par la droite.
J'ai pris comme noeud courant 5
0 2147483647 2147483647 2147483647 2147483647 2147483647 
0 3 1 2147483647 2147483647 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 6 2147483647 
0 2 1 4 5 7 
0 2 1 4 5 6