Discussion :

[dalilnet]

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

[pseudocode]

Est-ce que cette discussion pourrait t'aider ?

http://www.developpez.net/forums/d64...hemins-graphe/

[SpiceGuid]

À 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.