Theorie des graphes : chemins multiples dans un DAG

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

[fatal_error]

salut,

en utilisant une matrice de chais plus quoi (adjacente en fait im semble, genre booléenne qui exprime les relations entre les noeuds), t'as une matrice a priori pas symetrique. Et a priori, elevée a la puissance n, tauras toujours des 0 sur la diago pour dire que ya pas de cycles.

L'idée, c'est que pour chaque multiplication que tu fais, ben t'enregistres chaque cellules ou ya pas de 0, ce qui constitue un chemin.
Et en gros, tu concatenes le chemin de la matrice de gauche, avec ceux de la matrice de droite, avec un cartesien ou qqch dans ce genre.

L'autre alternative bien bourrine, ben c'est de faire un algo en profondeur que tu appliques sur chaque noeuds lol. Et a chaque fois que tu te rappele, tenregistres le chemin.

Sinon, si tu voulais un nom, je n'en connais pas. Pour la matrice d'adjacence, tu peux optimiser le calcule (encore qu'on sen branle avec tous les enregistrements pour lister qui prennent du temps) avec du warshall floyd, et sinon l'autre ben c'est parcours de graphe en profondeur... mais ce sont des algo qu'on bidouille, pas qui fournissent la solution directe a ton probleme à proprement parler.