bonjour, je doit realiser un programme permettant de calculer les plus courts chemins d'un graphe, eventuellement avec une marge supplémentaire tolérée. j'ai donc appliqué dijktra pour trouver le plus court, ainsi que sa longueur, mais pour les autres je patauge un peu, quelqu'un connait il un algo existant pour calculer tous les chemins de longeur <= à une valeur donnée ?

Essaie ça:
Avec Dijkstra, on obtient le plus court court chemin d'un sommet du graphe vers tous les autres. C'est une bonne chose qui va nous servir.
Soit D(a,i) le chemin de longueur minimum entre a et i (calculé par Dijkstra) et c(i,j) le poids d'une arêtes entre i et j.
a est le sommet de départ et b le sommet de destination.
 
Partons du sommet de destination b. Soit x le sommet précédent b sur le meilleur chemin. Il y a deux cas possibles:
1) Soit le dernier arc du 2ème meilleur chemin ne provient pas de x, dans ce cas le coût du 2ème meilleur chemin est D'(a,b)=min(D(a,i) + c(i,b)) pour tous les précédents i du sommet b différents de x.
2) Soit le dernier arc est identique et provient de x. Dans ce cas on peut se ramener au problème de trouver le 2ème meilleur chemin vers x. Le coût total jusque b sera alors D'(a,x)+c(x,b) où D'(a,x) est le coût du second meilleur chemin jusque x.
 
Autrement dit, pour chaque sommet du meilleur chemin (sauf l'origine bien sûr), on va essayer de prendre un autre précédent. Parmi tous ces chemins alternatifs, celui de coût le plus faible sera le 2nd meilleur chemin.
 
Pour le 3ème meilleur chemin, je ne suis pas certain à 100% mais je pense que ce sera soit un des chemins alternatifs du meilleur chemin (déjà calculés) ou un chemin alternatif du second meilleur chemin (qu'on obtient de la même façon). Et ainsi de suite pour le 4ème, 5ème, etc...

merci pour la reponse, ça ressemble bien a ce que je pensait, j'utilise le resultat de dijkstra, pour parcourir le graphe a l'envers en verifiant a chaque fois les sommets voisins. par contre apres pour le 1) je ne comprend pas trop, et j'ai l'impression qu'on aura qu'un nombre fixé de chemins, mais il peux y en avoir plein, surtout avec la marge supplémentaire. voici ou j'en suis :
 
 

 
 
lancé par l'insturction

 
matriceArcs donne les distances entre les arcs (-1 si non reliés); pDepart est la position de depart, pareil pour l'arrivée; m est la marge; chemin contient un chemin (il y aura donc autant de vecteurs que de resultats; tousLesChemins cntient tous les chemins.
 
la le probleme est le suivant : il oublie certaisn chemins, visiblement ceux pour elsquels on doit parcourir le tableau donné par dijkstra en sens inverse. (on parcous un chemin dans un sens alors que si on part de l'un de ses points, le plus court chemin passe en sens inverse). a part ça ça marche.