Forum Clubic

Problème de plus court chemin

Bonjour,
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 au moins k sommets. C’est cette dernière condition qui me pose problème. Je pensais utiliser une recherche en profondeur (Depth First Search). Le problème est comment modifier cet algorithme pour passer par au moins k sommets?
Merci d’avance

Ben je suppose que c’est le même algo que celui des plus courts chemins, sauf que si ton plus court chemin n’est pas passé par k sommets, tu continue?

Si tu donnes l’algo initiales, je pourrais voir :slight_smile: (pas envie d’aller googler pour ça moi :))

J’imagine. L’algo est assez court:

DFS (graphe G, sommet s):
{
Marquer(S);
debut
POUR CHAQUE élément sfils de Voisin(s) FAIRE
SI NonMarqué(sfils)
ALORS DFS(G,sfils);
FIN-SI
FIN-POUR
fin
}

Voisin(s) : renvoie la liste des sommets adjacents à s.
Marquer(Nœud ) : marque un nœud, de manière à ne pas le considérer plusieurs fois.
SousArbre(nœud u) : retourne le sous-arbre de racine u.

Voila pour l’algo. Sinon pour les problème de plus court chemin il y a évidemment dijkstra mais on m’a laissé entendre que l’on ne pouvais imposer un nombre de sommets.

Vu que Dijkstra c’est de la récursivité, je suppose qu’il te faudra le passer en paramètre et avoir un compteur que tu incrémenteras à chaque fois.

et avec celui que je t’ai mis, il y a rien à faire. J’avoue être un peu perdu. Il faudrait rajouter une condition imposant un nombre de sommet, ça doit être jouable non?