1 pièce(s) jointe(s)
Algorithme de Ford-Bellman
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:
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:
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.
