Discussion :

[Raiden1234]

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 Java :

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
 
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 Java :

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
 
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 Java :

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

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 Java :

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

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.

[PRomu@ld]

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...)

Le mieux est encore de faire du print à tout va (c'est une des meilleure méthode de debuggage bas niveau)

Affiche ton tableau avant de rentrer dans ta boucle. Et affiche ce qui se passe dans ton if (par exemple si tu rentres dans le if affiche la valeur, ce pourquoi tu es rentré dans le if, ...

[borisd]

La structure de la fonction coutMinNonTraite est plutôt bizarre : tu sembles comparer la valeur de l'entrée courante (1) avec la valeur de l'entrée suivante (2), pour garder la meilleure des deux. Malheureusement, tu oublies laquelle c'est à l'itération suivante, et tu compares l'entrée (2) avec la (3), sans connaître la valeur de (1).
Par ailleurs, même si tu te resservais de la meilleure valeur connue (dans la variable "ent" je suppose) dans la deuxième partie de ta boucle, la première (ci-dessous) l'écrase :

Code :

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

1
2
3
4
5
 
if (tb.get(i).isTraite() == false && test == true) {
                ent = tb.get(i);
                test = false;
            }

[PRomu@ld]

C'est exact.