Discussion :

[jon48]

Bonjour,

Dans le cadre d'un projet, je possède une cartographie d'une entreprise que je modélise par un graphe (les sommets sont les différente blocs de l'entreprise et les arcs les relations entre eux). Le graphe est a priori non orienté.

Sur ce graphe, j'ai une formule pour laquelle j'ai besoin de lister les chemins de longueur p (p quelconque), un même sommet pouvant apparaître plusieurs fois. Mon cours de théorie des graphes est un peu loin (j'ai de vagues souvenirs que le nombre de chemins est la trace de A^p, A étant la matrice d'adjacence), donc j'en appelle à vous pour m'aider à trouver l'algorithme qui me permettrait d'avoir la liste de ces chemins de longueurs p.

Par contre, cet algorithme est-il applicable en un temps raisonnable (j'ai de 20 à 30 sommets dans mon graphe) ?

Si je n'ai pas été assez clair dans mon explication, n'hésitez pas à me faire préciser des choses.

Merci d'avance.

[PRomu@ld]

Avec un parcours en largeur tu détermines directement les chemins de longueur 1, 2 , 3 ... Et ceci directement.

Par contre, cet algorithme est-il applicable en un temps raisonnable (j'ai de 20 à 30 sommets dans mon graphe) ?

Aucun soucis, même avec une centaine de sommets.

[jon48]

Bonsoir,

Je vous remercie pour cette réponse, et je vais essayer d'implémenter tout ça.

Bien cordialement,