Bonjour,

Dans le cadre d'un projet, je dois coder (en java) une heuristique permettant de trouver le plus court chemin dans un graphe d'un point s à un point t sous deux contraintes:

1ere : Le chemin doit passer par k sommets minimum. (Nombre k imposé par le graphe)

2eme : Certains sommets du graphe font parti de sous-ensembles, passer par un des sommets appartenant à un sous-ensemble m'oblige à passer par tous les sommets du sous-ensemble.

J'hésite entre une modification de l'algorithme de Dijkstra ou une modification de l'algorithme de recherche en profondeur...

Qu'en pensez vous?