Discussion :

[genetin]

Bonjour,

J'aimerais savoir si il existe un algorithme pour lister tous les chemins multiples qui existent dans un graphe orienté acyclique (DAG : directed acyclic graph).

Merci de votre aide.

[Champialex]

Je ferais un truc u genre :
je choisit un sommet de départ d et d'arrivé a
ensuite, je marque chaque arrête qui part de d, je choisit un sommet à l'extrémité d'une des arrêtes et je démarque cette arrête, puis je marque chaque arrête qui part de ce sommet ect...
Lorsqu'il n'y a plus aucune arrête marquées qui part d'un sommet, ou lorsqu'on est arrivé au sommet a, on fait : si on est sur a, on enregistre le chemin, et dans tout les cas on revient au sommet précédent et on explore les autres arrêtes marquées.
L'algo est terminé lorsqu'il n'y a plus aucune arrête marquées au sommet d.
Voila!
Sinon pourquoi as tu besoin de ça? Est-ce vraiment nécessaire de trouver tout les chemins??

[Invité]

Attention, le graphe est orienté, donc il est possible que d soit aussi un point d'arrivée de chemin(s) qui partirait d'on ne sait où. Donc la liste est terminée quand tous les arcs ont été parcourus.
Mais si le point de départ d n'est pas le seul point de départ d'un noeud, il peut y avoir plusieurs solutions, ce qui ne semble pas pertinent, puisque le graphe est orienté.
Donc, moi je partirais d'un point d qui ne peut pas être aussi un point d'arrivée.
Il y a aussi la notion de "chemin multiple" qu'il ne faut pas oublier. Un chemin ne sera à lister que s'il comporte au moins 2 arcs. (et que a et d sont différents, mais c'est dans l'hypothèse)
J'aimerais bien aussi connaître le domaine d'utilisation,si ce n'est pas confidentiel.

[Champialex]

Oui mais le graphe est acyclique... On ne peut pas par définition revenir à d. Les arrêtes qui y arrivent importe peu. A moins que tu veuille dire qu'il existe d'autres chemins... Effectivement, je ne l'ai pas marqué car ca me semblait évident, mais il faut en plus parcourir toute les paires (d,a) possibles.

[Champialex]

Donc, moi je partirais d'un point d qui ne peut pas être aussi un point d'arrivée.

Oui effectivement, bien vu, et dans ce cas, il faudrait l'appliquer à chaque composante connexe! Les autres chemins ne peuvent alors qu'être des sous-chemins de ceux qu'on obtiendra.

[Invité]

De toute façon, c'est pas simple. A priori, rien n'interdit de passer deux fois par le même arc, en partant de deux point d (départ) différents, ou même du même point de départ, avec un autre arc, ou même le même arc de départ, mais avec une autre bifurcation en cours.
Un graphe est un outil, on ne peut vraiment l'utiliser que si on sait le but à atteindre, ce qui n'est pas le cas présentement. Mais c'est un outil extraordinaire, je l'ai utilisé entre autres pour définir le meilleur chemin d'un point à un autre.

[genetin]

Merci beaucoup. Toute cette discussion me donne une bonne piste pour écrire l'algo.
Je vais m'y atteler.