Bonjour !

Je suis confronté au problème suivant :

J'ai N sommets numérotés de 1 à N, on associe à chaque couple de sommets un coût, c'est le coût du chemin les reliant. L'objectif est de trouver le chemin de longueur N passant par N sommets distincts tel que ce chemin soit le moins coûteux possible.
Jusque là il me semble -je suis novice en informatique- que plusieurs algorithmes permettent de répondre au problème, par exemple l'algorithme de Bellman-Ford
Sauf que j'ai une contrainte supplémentaire :
A chaque étape d'un chemin de longueur N on a un certain nombre de sommets accessibles et une fois qu'on a choisi un sommet alors celui-ci n'est plus accessible pour la suite puisqu'on veut passer par N sommets distincts. En fait c'est comme si le graphe évoluait pendant la simulation

Par exemple, pour N=5, on peut imaginer la liste suivante : [[1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5], [2, 3, 4, 5], [3, 4, 5]] donnant, pour chaque étape, la liste des sommets disponibles (pour l'étape 1 on ne peut choisir que parmi les sommets 1,2,3 , pour l'étape 2 on choisit parmi 1,2,3,4 en enlevant le sommet choisi à l'étape 1 et ainsi de suite...)

Pour résoudre ça, je vous avoue que je suis légèrement à court d'idées
Je pense que mon problème n'est pas non plus très original donc j'aimerais savoir si il existe des algorithmes pouvant le résoudre (sans énumérer toutes les solutions bien sûr). Ou alors, est-il possible d'adapter l'algorithme de Bellman-Ford à mon problème ?
Je suis également preneur de la moindre idée

Merci beaucoup pour votre aide !