Discussion :

[moi88]

Bonjour,

Je dois développer un simulateur qui calcule le plus court chemin entre deux noeuds.

J'ai le code suivant:

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
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
protected void dessinerChemin(chemin c,boolean coloree){
  Graphics g=dessin.getGraphics(); //lecomposant graphic utilisé pour dessiner
  if(coloree)
    g.setColor(new Color(255,0,0));
g.drawLine(c.ext[0].x,c.ext[0].y,c.ext[1].x,c.ext[1].y);
int a=c.ext[0].x+(c.ext[1].x-c.ext[0].x)/2;
int b=c.ext[0].y+(c.ext[1].y-c.ext[0].y)/2;
g.setColor(new Color(1000));
g.drawString(""+c.d,a,b);
}
 
public noeud[] noeudsDe(noeud n) {
    noeud tab[];
    //nombre des noeuds reliee a n
    int nbr=0;
    for(int i=0;i<nbrC;i++){
       if(((tabC[i].ext[0]==n)&&(tabC[i].ext[1].fermee==false))||((tabC[i].ext[1]==n)&&(tabC[i].ext[0].fermee==false)))
        nbr++;
    }
    tab=new noeud[nbr];
    //
    int j=0;
    for(int i=0;i<nbrC;i++){
      if((tabC[i].ext[0]==n)&&(tabC[i].ext[1].fermee==false)){
            tab[j] = tabC[i].ext[1];
        j++;
      }else if((tabC[i].ext[1]==n)&&(tabC[i].ext[0].fermee==false)){
            tab[j] = tabC[i].ext[0];
        j++;
      }
    }
    //return
    return tab;
  }
 
 
  public chemin cheminDe(noeud n1,noeud n2){
    chemin c=null;
    for(int i=0;i<nbrC;i++){
      if(((tabC[i].ext[0]==n1)&&(tabC[i].ext[1]==n2))||((tabC[i].ext[1]==n1)&&(tabC[i].ext[0]==n2)))
        c=tabC[i];
    }
    //return
    return c;
  }
  public boolean toutesLesNoeudsSontFermees(){
    boolean Fermees=true;
    for(int i=0;i<nbrN;i++){
      if(tabN[i].fermee==false)
        Fermees=false;
    }
    return Fermees;
  }
  public noeud leMinDe(noeud n){
    noeud leMin =noeudsDe(n)[0];
 
      float min = leMin.d;
      for (int i = 0; i < noeudsDe(n).length; i++) {
        if ( (noeudsDe(n)[i].fermee == false) && (noeudsDe(n)[i].d < min)) {
          leMin = noeudsDe(n)[i];
          min = noeudsDe(n)[i].d;
        }
      }
    return leMin;
  }
//et celui la est l'algorithme de dijkistra
 
//Algorithme; calculer et afficher le pcc
  //calcul
    //etape 1:
    for(int i=0;i<nbrN;i++){
      tabN[i].d=INFINITE;//c a d :l'infinit
      tabN[i].p=null;
      tabN[i].fermee=false;
    }
    I= tabN[s];
    I.d=0;
    I.p=null;
    I.fermee=true;
 
    //etape 2:
    do{
      K=I;
      noeud tmpN[]=noeudsDe(K);
      for(int j=0;j<tmpN.length;j++){
        if (!tmpN[j].fermee) {
          if (tmpN[j].d > (K.d + cheminDe(K, tmpN[j]).d)) {
            tmpN[j].d=Math.min(tmpN[j].d,(K.d+cheminDe(K,tmpN[j]).d));
            tmpN[j].p = K;
          }
          tmpN[j].d=Math.min(tmpN[j].d,K.d+cheminDe(K,tmpN[j]).d);
        }
      }
    //etape 3:
    if(!toutesLesNoeudsSontFermees()){
     /* try{*/
        I = leMinDe(K);
        status.setForeground(Color.gray);
        status.setText("OK");
      /*}catch(ArrayIndexOutOfBoundsException aioobe){
        status.setForeground(Color.red);
        status.setText(aioobe.toString()+"Erreur : "+K.nom+".");
        break;
      }*/
      //etape 4:
      I.fermee = true;
    }
  }while(!toutesLesNoeudsSontFermees());
  //désignler les chemins
  for(int i=0;i<nbrC;i++){
      tabC[i].signalee = false;
  }
  //signler les chemins
  for(int i=0;i<nbrN;i++){
    if(tabN[i].p!=null)
      cheminDe(tabN[i],tabN[i].p).signalee = true;
  }
  //affichage
  for(int i=0;i<nbrC;i++){
    if(tabC[i].signalee){
      dessinerChemin(tabC[i],true);
    }
  }
  //status
  }

Cet algorithme me permet d'afficher le plus court chemin entre le noeud source et tous les autres noeuds.

Quelqu'un aurait-il un solution à me proposer pour pouvoir afficher le plus court chemin entre 2 noeuds source et destination ?

Merci d'avance pour votre aide.

[Vikisme]

Bonjour,

Si je comprends bien la question, tu sais retrouver le chemin le plus court entre un noeud et tous les autres, et tu veux retrouver le chemin le plus court entre un noeud et un autre ?

Sur wiki on trouve différents algorithmes pour ça : Algorithmes du plus court chemin et plus particulièrement l'algorithme de Dijkstra.

[moi88]

Si je mets un autre algorithme, je dois modifier la totalité de code.
Moi je veux juste modifier dans le code de Dijkistra que j'ai, pour avoir ce résultat (chemin minimal entre 2 nœuds).