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
| public void autresChemins(Vector sommets,int T[][],int d,int p,int m,Vector v,
int prec) {
Vector chemin=new Vector();
for (int i=0; i<v.size(); i++) // on recopie le chemin deja parcouru
chemin.add(v.elementAt(i));
while(p!=d) {
chemin.insertElementAt(sommets.elementAt(p),0);
for (int i=0; i<sommets.size(); i++)
// un chemin secondaire ne doit pas revenir sur le sommet precedent, ni
// suivre le plus court chemin, et avoir un poids pas trop elevé
if (matriceArcs[i][p]!=-1 && i!=T[1][p] && i!=prec &&
(m>(T[0][i]+matriceArcs[i][p]-T[0][p])))
{
m=m-T[0][i]-matriceArcs[i][p]+T[0][p];
autresChemins(sommets,T,d,i,m,chemin,p);
}
// cas du cul de sac : si on est revenu en arriere, on arrete
// le parcours et efface le chemin parcouru
if (chemin.size()>2 && chemin.elementAt(0)==chemin.elementAt(2)) {
chemin.removeAllElements();
break;
}
prec=p;
p=T[1][p];
}
chemin.insertElementAt(sommets.elementAt(p),0);
if (chemin.size()>1)
for (int i=0;i<chemin.size();i++)
tousLesChemins.add(chemin.elementAt(i));
} |
Partager