Discussion :

[cashp]

Bonjour à tous,

Je viens chercher un peu d'aide pour une question qui me turlupine depuis quelques jours (en fait là j'en suis presque à m'arracher les cheveux )...

En effet, admettons un graphe orienté avec un ensemble de sommets et d'arcs orientés. Ce que je cherche à faire avec ce graphe, c'est "tout simplement" déterminer s'il y a un chemin multiple. Ce que j'appelle chemin multiple est par exemple pouvoir aller du sommet 1 au sommet 3 par plusieurs chemins (chemin = ensemble d'arcs).

Exemple avec une liste d'arcs comme ceux-ci :
1->2
1->3
2->3
1->4
4->3

Avec ce graphe orienté, il y a 3 manière d'aller de 1 à 3.
Donc ce que je cherche c'est un algo qui permettrait de détecter dans un graphe orienté s'il y a des chemins multiples (je ne veux pas savoir leur nombre ni leur origine et extrêmité).
J'ai beaucoup réflechi sur le sujet, et je pense que la solution se trouve en utilisant l'algorithme de parcours en profondeur, mais j'ai beau chercher, je ne vois pas comment le modifier/exploiter pour résoudre mon problème...
Donc si l'un d'entre vous aurait une piste à suivre, je serais très reconnaissant parce que je suis à deux doigts de me taper la tête contre les murs

Merci beaucoup !

[mchk0123]

Bon, je ne suis pas sur de ce que j'avance, mais dans le cas ou tes chemins multiples sont disjoints (comme dans l'exemple), tu peux essayer ceci :

- lancer un parcours en profondeur (ou en largeur ?)
- si tu trouve un chemin de 1 à 3 (ie. la récursion se termine sur 3),
tu retire de ton graphe tous les arcs de ce chemin
- tu relance le parcours une 2ème fois
- si tu trouve de nouveau un autre chemin, c'est qu'il existe au moins 2 chemins disjoint

[cashp]

Bon, je ne suis pas sur de ce que j'avance, mais dans le cas ou tes chemins multiples sont disjoints (comme dans l'exemple), tu peux essayer ceci :

- lancer un parcours en profondeur (ou en largeur ?)
- si tu trouve un chemin de 1 à 3 (ie. la récursion se termine sur 3),
tu retire de ton graphe tous les arcs de ce chemin
- tu relance le parcours une 2ème fois
- si tu trouve de nouveau un autre chemin, c'est qu'il existe au moins 2 chemins disjoint

Qu'est-ce que des chemins disjoints ?
Le problème est que quand je lance le parcours, je ne sais pas s'il existe un chemin mutliple et encore moins entre quels sommets donc comment savoir si je retire les arcs ?

Ton idée est peut -être bonne mais je n'ai tout simplement pas tout saisi (les graphes c'est vraiment trop abstrait pour moi !).

[mchk0123]

Deux chemins sont disjoints s'il n'ont en commun aucun point (sauf le point de départ et le point d'arrivée bien sur).

[cashp]

Deux chemins sont disjoints s'il n'ont en commun aucun point (sauf le point de départ et le point d'arrivée bien sur).

Dans ce cas mon exemple était mauvais, les chemims multiples ne sont pas forcément disjoints.

[Nemerle]

Si tu notes M[i,j] ta matrice d'adjacence (qui vaut 1 en i,j si tu as une arrête i-->j, 0 sinon), alors le nombre de chemins de longueur p de i à j est donné par le coefficient (M^p)[i,j].

Pour rappel, (M^p)[i,j] est la somme des (M^(p-1))[i,k] * M[k,j] sur k.

Ci-joint un lien sympa qui te précise tout ça: http://www.dix.polytechnique.fr/IF/poly/main003.html

[FrancisSourd]

Pour connaître le nombre de chemins entre deux sommets de ton graphes tu calcul le flot maximal entre ces deux sommets en mettant des capacités égale à 1 sur les arcs. Si tu ne connais pas les flots max, regarde par exemple
http://lapoire.developpez.com/algorithmique/graphes/ (Chapitre 10)

NB: Le nombre de chemins ici est le nombre maximal de chemins qui n'ont pas deux arêtes en commun.

[mchk0123]

Je ne sait pas ça peut-être suffisant, mais le problème de la taille des matrices d'adjacence peut être réduit en utilisant des matrices éparses pour le stockage (typiquement remplies de beaucoup de 0).

Voilà voilou ...

[cashp]

Bon, j'ai une solution qui a l'air de marcher, en tous cas je ne l'ai pas encore prise en défaut

J'aurais donc un petit coup de pouce à vous demander concernant une autre question. Si on considère un graphe orienté dans lequel il n'y a pas de chemins multiples (mais il peut y avoir des cycles par contre), comment peut-on déterminer le chemin le plus long dans tout le graphe (aucun sommet source ou extrêmité n'est donné, ils sont quelconques) ?

[FrancisSourd]

J'aurais donc un petit coup de pouce à vous demander concernant une autre question. Si on considère un graphe orienté dans lequel il n'y a pas de chemins multiples (mais il peut y avoir des cycles par contre), comment peut-on déterminer le chemin le plus long dans tout le graphe (aucun sommet source ou extrêmité n'est donné, ils sont quelconques) ?

Le problème du plus long chemin dans un graphe orienté est un problème NP-complet. Un cas particulier de ce problème est le problème du chemin hamiltonien.

S'il n'y a qu'un chemin entre deux paires de points, tu peux calculer la longueur de ce chemin pour les n² paires de chemin et retourner le plus long chemin trouvé.

[Nemerle]

On peut effectivement se passer de la matrice d'adjacence. Tu peux calculer (M^p)[i,j] directement à partir de tes listes.

Donne-moi le format de tes listes, je te donnerai un algo si tu veux