Bonjour tout le monde,

J'ai un problème que j'ai essayé d'assimiler au problème du « plus court chemin » sous contraintes :



On doit passer obligatoirement par chaque ensemble et, dans chaque ensemble, on doit passer seulement par une ellipse.

les contraintes peuvent être (à titre d'exemple) :

  • passer par les ellipses rouges au maximum 2 fois ;
  • passer par les ellipses vertes au maximum 3 fois ;
  • passer par les ellipses bleues 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.
Merci d'avance.