bonjour, je fais en ce moment un programme (en Java) pour determiner le plus court chemin dans le metro. j'ai alors utilisé dijkstra. jusque la tout va bien ca fonctionne.
mais je dois aussi donner la possibilité de donner tous les plus courts chemins en cas d'egalité, et dijktra n'en donne qu'un. et pour compliquer encore plus, il faut introduire une marge possible (par exemple : chercher tous les chemins de meme longueur que le plus courts trouvé, a +5% de trajet en plus pres). j'ai alors programmé la chose suivante :


Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
public void autresChemins(Vector sommets,int T[][],int matriceArcs[][],int d,
    										int p,int m,Vector tousLesChemins) {
    	for (int i=0; i<sommets.size(); i++)
    if ((matriceArcs[i][p]!=-1)&& (T[0][i]+matriceArcs[i][p])<=(T[0][p]+m))
    	    		    {
    			tousLesChemins.insertElementAt(sommets.elementAt(i),0);
    			if (i!=d) {
    				m=m+T[0][i]+matriceArcs[i][p]-T[0][p];
    				autresChemins(sommets,T,matriceArcs,d,i,m,tousLesChemins);    				
    			}
    		}
    }

cela marche bien dans les cas favorables, mais il y a des cas ou il me sort l'erreur : "stack overflow"
si un arc est a 0 dans les 2 sens; ou si la marge est trop grande

T[][] est le tableau récupéré dans dijstra : cela donne la distance au sommet de depart, et le sommet precedent. d est le depart, p l'arrivée; m la marge, tousLesChemins le tableau de resultats; matriceArcs[][] le tableau de spoids des arcs.

voyez vous comment faire ?