Discussion :

[edbuffer]

Bonjour,

Je voudrais utiliser cet algorithme de Ford-Bellman pour obtenir le chemin maximum du sommet A au sommet K dans un graphe orienté.

Voici mon code :

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
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
 
#include <iostream>
using namespace std;
 
typedef struct {
	int u, v, w;
} Arc;
 
int n;			//nombre de sommets
int e;			//nombre d'arcs
Arc arcs[32];      //tableau de 32 arcs maxi
int d[32];		//tableau des valeurs des distances aux noeuds situés à chaque indices du tableau
 
//const int INFINITY=10000;
 
void printDist() {
	int i;
 
	cout << "Distances:" <<endl;
 
	for (i = 0; i < n; ++i)
		printf_s("au noeud: %c, on a un cout de :%d\n", '@' + i + 1, d[i]);
 
	cout << endl;
}
 
void bellman_ford(int s) {
	int i, j;
 
	// Initialiser la matrice des distances à 0
	for (i = 0; i < n; i++)
		d[i] = 0;
 
	d[s] = 0; // Valeur de la distance du sommet de départ
 
	// Pour chaque sommet
	for (i = 0; i < n - 1; i++)
		for (j = 0; j < e; j++) // Parcourir tous les arcs à la recherche de celui dont le cout est le + élevé
			if (d[arcs[j].u] + arcs[j].w > d[arcs[j].v])
				d[arcs[j].v] = d[arcs[j].u] + arcs[j].w;
}
 
int main(int argc, char *argv[]) {
	int i, j;
	int w;
	errno_t err;
	FILE *fin; // Fichier "dist.txt"
	try
	{
 
		err = fopen_s(&fin, "dist.txt", "r");
		if(err) cout << "Le fichier \"dist.txt\" n'a pas pu etre ouvert" << endl;
 
		fscanf_s(fin, "%d", &n);
		e = 0;
 
		for (i = 0; i < n; ++i) 
			for (j = 0; j < n; ++j) {
				fscanf_s(fin, "%d", &w);
				if (w != 0) {
					arcs[e].u = i; // Premier sommet de l'arc
					arcs[e].v = j; // Second sommet de l'arc
					arcs[e].w = w; // Valuation de l'arc
					++e;
				}
			}
 
 
		//printDist(); 
 
		bellman_ford(0);
 
		printDist();
 
	}
	catch(...){
		cout << "Il y a eu une erreur" << endl ;	
		fclose(fin);
	}
 
	return 0;
}

Et voici la matrice (du fichier "dist.txt"):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
11
0 2 0 0 0 10 0 0 15 0 0
0 0 5 0 0 0 25 0 0 0 0
0 0 0 10 0 0 0 50 0 0 0
0 0 0 0 25 0 0 45 0 0 0
0 0 0 0 0 0 0 0 0 0 15
0 0 0 0 0 0 40 0 20 0 0
0 0 0 0 0 0 0 20 0 0 0
0 0 0 0 15 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 5 0
0 0 0 0 20 0 0 0 0 0 45
0 0 0 0 0 0 0 0 0 0 0

Le fait est que pour calculer le chemin minimum, il marche bien, mais pr le chemin maxi, le résultat est faux et j'ai bien l'impression qu'il fait ses tests en colonne au lieu de les faire en ligne. C'est peut être ma façon de faire la matrice qui est fausse ?

Je place le dessin du graphe en question en pj.

Est ce que vous voyez l'erreur s'il vous plait ?

Merci d'avance pour votre aide.

[3DArchi]

Bonjour,
Outre que ton code est un affreux mélange de C et de C++, je te conseille de rajouter quelques traces pour voir ce qu'il se passe à chaque étape de ton algo. Cela te permettra d'identifier plus rapidement le problème.
Bon courage.

[poukill]

Mélange horrible en effet.
De C++ il n'y a que le try / catch, très mal utilisé; et une en-tête (iostream, alors que tu utilises printf ! )
Avec en prime des variables globales !

Plus sérieusement, je te conseille de jeter un coup d'oeil sur un bon cours C++ (livre ou bien ressources Developpez.com) si tu veux écrire quelque chose de correct.
Après, si tu veux juste finir vite, suit le conseil de 3DArchi ci dessus.

Bonne continuation,

Poukill

[edbuffer]

Merci je regarde,
Bon j'ai pas tte la nuit mais à priori pr l'algo c'est bon sur le principe.
Niveau affreux mélange, je peux faire mieux et je reposterai + tard au sujet du fabuleux c++...

Et merci encore pr les réponses
@+