Discussion :

[WileECoyote]

Bonjour,

Je recherche un algorithme qui me permettrait de rechercher, dans un réseau completement maillé, le plus court chemin entre deux points en y mettant des contraintes :

- un poid entre 2 noeuds (pour rester dans le classique)
- des noeuds obligatoires (ou l'on doit forcément passer)
- un nombre de noeud minimum a traverser
- on ne passe par un noeud qu'une seule fois

Peut-etre que quelqu'un a déjà réfléchi a ce genre de truc tordu
Le problème s'écarte un peu des algos traditionnels du genre comme Dijkstra ou A* et je galère un peu.

Je précise que je cherche cet algorithme pour des besoins personnels, que ce n'est pas dans un cadre scolaire et qu'il n'est pas question d'en faire commerce !

Si certains d'entre vous ont des pistes, je suis preneur !

[chrissou]

Tu pourrais faire plusieurs Dijkstra entre les points obligatoires peut-etre?
Mais il faudrait trouver l'ordre de passage optimal par les points obligatoires préalablement.