Problème de plus court chemin

Titiene
Messages postés
5
Date d'inscription
mercredi 6 février 2008
Statut
Membre
Dernière intervention
30 mars 2009
- 12 mars 2009 à 13:42
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
- 30 mars 2009 à 16:21
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

8 réponses

coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
41
12 mars 2009 à 21:38
non dijkstra te trouvera le plus court chemin, mais il ne passera pas par k sommets.

tu dois faire une simple recherche en profondeur
0
Titiene
Messages postés
5
Date d'inscription
mercredi 6 février 2008
Statut
Membre
Dernière intervention
30 mars 2009

16 mars 2009 à 14:56
On ne peut pas rajouter une condition ou une contrainte dans l'algorithme de Dijkstra pour justement qu'il passe par un nombre de sommets donnés
0
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
41
16 mars 2009 à 15:21
non
0
Titiene
Messages postés
5
Date d'inscription
mercredi 6 février 2008
Statut
Membre
Dernière intervention
30 mars 2009

16 mars 2009 à 15:27
Et tu n'as pas une piste, car pour être honnête je ne comprends pas trop la simple recherche en profondeur. 
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
41
16 mars 2009 à 15:38
tu peux chercher ca sur google :

recherche en profondeur
deep first search
0
Titiene
Messages postés
5
Date d'inscription
mercredi 6 février 2008
Statut
Membre
Dernière intervention
30 mars 2009

30 mars 2009 à 14:35
merci!! Ca m'evite une fausse piste, mais le probleme reste le même, à savoir comment imposer le passage par sommets.
0
Titiene
Messages postés
5
Date d'inscription
mercredi 6 février 2008
Statut
Membre
Dernière intervention
30 mars 2009

30 mars 2009 à 14:37
merci!! Ca m'evite une fausse piste, mais le probleme reste le même, à savoir comment imposer le passage par k sommets.
0
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
41
30 mars 2009 à 16:21
comme je l'ai dit, tu peux faire une recherche en profondeur.


il me semble que google est assez complet sur ce point.
0