"le plus court chemin" sous contraintes

[sarmad354]

bonjour tout le monde
j'ai un problème que j'ai essayé de l'assimiler au problème "le plus court chemin" sous contraintes

les contraintes peuvent être ( à titre d'exemple):
on doit passer par un ellipse et seulement un dans chaque ensemble
passer par les ellipses rouges au maximum 2 fois
passer par les ellipses verts au maximum 3 fois
passer par les ellipses bleus au maximum 2 fois
passer par les ellipses jaunes au maximum 2 fois

ma question est de trouver l'algorithme pour déterminer le plus court chemin??
et merci d'avance

 

[Gorfael]

Re : "le plus court chemin" sous contraintes

Salut sarmad354 et le forum
Pour me répeter, on n'est ni devant ton écran, ni dans ta tête et on ne sait du problème que ce que le sujet donne.

Donc, avec les infos, un trajet de 5 liaisons est le plus court et le seul chemin .
A+

 

[sarmad354]

Re : "le plus court chemin" sous contraintes

merci Gorfael

le graphe donné juste pour se mettre au bain

je note que :

-le nombre des ensemble ne se limite pas à 4, mais en réalité peut dépasser 100
-le nombre des ellipses dans chaque ensemble ne se limite pas 4, mais en réalité peut dépasser 100
-on peut pas trouvé deux ellipse de même couleur dans chaque ensemble.