Je cherche un algorithme en java pour trouver le chemin le plus court chemin dans un graphe orienté allant du sommet 1 au sommet n et passant par k sommets. C'est cette dernière condition qui me pose problème. Je pensais utiliser évidemment l'algorithme de dijkstra. Qu'en pensez vous? Et comment modifier ce dernier pour passer par k sommets?
Merci d'avance

Apparemment, il serait préférable d'utiliser une recherche en profondeur plus couramment appelée deep first search. Le problème reste le même à savoir comment le modifier afin de passer par k sommets.

Quand tu dis "passer par k sommets", tu veux dire que tu recherches un chemin partant d'un sommet donné s et allant à un autre sommet t donné et de taille au moins k, ou bien allant de s à t et passant par au moins chaque sommet d'un ensemble K ?

Je recherche le chemin allant du sommet s au sommet t et passant par k sommets distincts. C'est à dire, qu'il faut imposer un nombre exact de k sommets.

Dans ce cas, effectue un parcours de ton graphe à la Dijkstra et au lieu de mémoriser le chemin le plus court pour chaque sommet, mémorise l'ensemble des chemins menant à ce sommet avec leur longueur en terme de noeuds distincts.  
 

Car on m'a laissé entendre que l'on ne pouvait le modifier, d'où l'utilisation d'une recherche en profondeur