Petit problème avec l'algorithme de Dijkstra
Bonsoir,
alors voila j'essaye d'implémenter l'algorithme de Dijkstra en Java.
J'ai bien compris le principe qui consiste à utiliser une table de donnée composé des propriétés "noeud", "traité", "coût" et "chemin" qu'il faudra d'en un premier temps initialiser. Puis, remplir et enfin reparcourir en partant de la fin pour déterminer le plus court chemin.
J'ai implémenter tout cela à travers des méthodes cependant voila j'ai une méthode qui permet de déterminer le coût non traité le plus faible de ma table de donnée, et aussi surprenant que cela peut-être, d'après l'exécution de mon programme, cette fonction retourne le coût le plus élevé ?? Je ne comprends vraiment pas le problème car la méthode me semble clairement juste (j'ai vérifié une dizaine de fois si je n'avais pas inversé de signes, etc...)
Voici cette méthode :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public Entree coutMinNonTraite(ArrayList<Entree> tb) {
Entree ent = null;
boolean test = true;
for (int i = 0; i < tb.size() - 1; i++) {
if (tb.get(i).isTraite() == false && test == true) {
ent = tb.get(i);
test = false;
}
if ((tb.get(i + 1).isTraite() == false) && (tb.get(i + 1).getCout() < tb.get(i).getCout())) {
ent = tb.get(i + 1);
}
}
return ent;
} |
Elle est utilisé dans ma fonction de remplissage de ma table :
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
|
public void parcourir(int[][] mat, ArrayList<Entree> table) {
System.out.println("\nDEBUT PARCOURS\n");
while (fini(table) == false) {
// 1
Entree temp = coutMinNonTraite(table);
temp.setTraite(true);
System.out.println("\nLe noeud " + temp.getNoeud() + " a le plus petit cout et vient d'etre validé");
// 2
for (int i = 0; i < this.nbSommet; i++) {
int coutCourant = mat[temp.getNoeud() - 1][i];
if (coutCourant > 0 && coutCourant < 10000) {
table.get(i).setCout(temp.getCout() + coutCourant);
table.get(i).setPred(temp.getNoeud());
System.out.println(" Le fils " + (i + 1) + " du noeud père " + temp.getNoeud() +
" a un cout de " + coutCourant + " et vient d'etre sauvé dans la table (mais non validé)");
if (i == this.somFin) {
table.get(somFin-1).setTraite(true);
}
}
}
System.out.println("----------------------------------");
}
System.out.println("\nFIN PARCOURS\n");
} |
Code:
1
2
3
4
5
6
7
|
public void initTable(int somDeb) {
for (int i = 1; i <= nbSommet; i++) {
this.table.add(new Entree(i, false, 10000, 0));
}
this.table.get(somDeb - 1).setCout(0);
} |
Code:
1
2
3
4
5
6
7
8
9
10
11
12
|
public boolean fini(ArrayList<Entree> table) {
boolean test = true;
for (int i = 0; i < table.size(); i++) {
if (table.get(i).isTraite() == false) {
test = false;
}
}
return test;
} |
Pour info, Entree correspond à une entrée de la table (composé de "noeud", "traité", "coût" et "chemin".
Voila je ne vois vraiment pas là où ça ne colle pas, j'ai suivi les étapes à la lettre
Merci de m'aider. ;)
