Discussion :

[ikob77]

Bonjour,
Je dois résoudre un exercice et je suis coincé :
Il s'agit d'un cercle dont la circonférence est divisée en N cases. Pour chacune des cases je devrais trouver le nombre de mouvements minimum pour aller de la case 1 à la case n (n allant de 1 à N).
Il y a trois types de déplacements :
- avancer un cran à droite
- reculer d'un cran vers la gauche
- emprunter un tuyaux qui se trouve sur la case

En effet, je possède un tableau qui à chaque case attribue le nombre de cases qu'elle me fait avancer vers l'avant si j'emprunte le tuyau qui se trouve sur celle ci.

Je pense que je me casse trop la tête à essayer de déterminer un chemin alors qu'il suffit de trouver le nombre de mouvements.
J'ai pensé a l'algo de Dijkstra, mais étant donné que lorsque je me trouve sur la dernière case numéroté je peut me déplacer vers la case 1 (on revient en arrière dans le graphe ?) je pense donc que cet algo n'est pas utilisable ici.

Auriez vous une idée quant a la façon de résoudre ce problème ?

[Matthieu Brucher]

Je pense que c'est un bon choix. Ton but est d'aller d'un point a à un point b dans un graphe orienté, aucun souci pour ton problème d'arc de B vers A.

[ikob77]

Ok merci !

Est ce que il serait possible d'avoir un exemple de l'algorithme de dijkstra qui correspond a mon problème, ou tout du moins pour le début quand on défini des matrices ou les structures parceque je suis un peu perdu. Je code en C.

[Matthieu Brucher]

Je ne peux pas trop te dire, c'est à toi de définir comment tu vas coder ton graphe ! Je te conseillerai de le faire sous la forme d'un tableau de listes.