Bonjour
je cherche un algorithme qui permet de générer tous les chemins possible entre deux point dans un graphe donné, je cherche pas le plus court chemin mais je veux tous les chemins
merci
Bonjour
je cherche un algorithme qui permet de générer tous les chemins possible entre deux point dans un graphe donné, je cherche pas le plus court chemin mais je veux tous les chemins
merci
Est-ce que cette discussion pourrait t'aider ?
http://www.developpez.net/forums/d64...hemins-graphe/
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
À mon avis il n'est pas très judicieux de simplement dresser une liste de tous les chemins de A à B en oubliant tout de la structure du graphe originel.
L'algo que tu voudras appliquer sur le résultat n'est probablement pas un algo sur les listes mais plutôt un algo sur les treillis.
La structure que tu veux extraire du graphe c'est le treillis borné par A et B.
Pour extraire ce treillis il suffit de parcourir le graphe avec une recherche taboo.
Une variante intéressante c'est le cas où le graphe est non-orienté, dans cas on peut faire une recherche taboo bidirectionnelle (exploration en largeur d'abord (breadth-first) à partir de A et à partir de B). Le cheminement bidirectionnel s'arrête lorsqu'un chemin venant de A rencontre un chemin venant de B. De cette façon on obtient un treillis où la distance (en nombre d'arêtes) entre A et B est constante et minimale, le tout en explorant un minimum de noeuds.
Autrement, un parcours en profondeur d'abord (depth-first) fait très bien l'affaire.
Du même auteur: mon projet, le dernier article publié, le blog dvp et le jeu vidéo.
Avant de poser une question je lis les règles du forum.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager