Nos principaux résultats ici sont les suivants. Nous proposons dans un premier temps un algorithme polynomial pour construire le plus court chemin entre deux sommets d'un graphe avec des transitions obligatoires. Nous montrons que déterminer la longueur minimale d'un parcours respectant les transitions obligatoires à partir d'une source, passant par $c$ cibles données en entrée est non-approximable pour toute constante, même dans le graphe complet à $n$ sommets $K_{n}$. De même, déterminer la longueur minimale d'un tel parcours passant par tous les sommets du graphe est non-approximable pour toute constante, même dans $K_{n}$. Le résultat précédent est étendu à la recherche d'un parcours hamiltonien (i.e. chaque sommet est parcouru une et une seule fois) suivant les mêmes conditions. Nous avons procédé à des réductions à partir du problème \textit{Restricted Exact Cover by 3-Sets} (\RXC) pour montrer ces non-approximations. Ses données sont un ensemble d'éléments $\mathcal{X}$ et une collection $\mathcal{C}$ de triplets de $\mathcal{X}$. Une solution au problème \RXC~est une sous-collection $C' \subset \mathcal{C}$ telle que chaque élément de $\mathcal{X}$ apparaît exactement une fois dans les triplets de $C'$.
 
 Nous montrons également que, pour toute constante $x \in \mathbf{N}^+$, déterminer s'il existe un cycle élémentaire, respectant les transitions obligatoires, de taille au moins $\sqrt[x]{n} > 4$ est $\mathcal{NPC}$ même dans $K_{n}$. La preuve s'appuie sur une réduction au problème du cycle élémentaire sans transitions obligatoires. Nous montrons aussi qu'aucun algorithme ne peut garantir trouver un cycle élémentaire de taille supérieure à deux (resp. trois) dans un complet $K_{n}$ orienté (resp. non orienté).