Modification d'algorithme dij
Bonjour,
Je dois développer un simulateur qui calcule le plus court chemin entre deux noeuds.
J'ai le code suivant:
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
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.
