Tout les chemins dans un graphe

[tunnour]

salut

J'ai un graphe orienté.
Je veux trouver tous les chemins d'un point A à un point B .
dans ce graphe chaque arc orienté de A vers H ( par exemple porte un poids).
je veux avoir à la fin une liste de tous les chemins possibles entre A et B avec le cumul des poids pour chaque chemin.


y a t'il un algorithme qui me permet de faire ce si?
merci pour tout aide
:cry: :help:

[fatal_error]

salut,

oui.
Tu cherches pour algo en profondeur d'abord ou algo en largeur d'abord. I sont sur wikipedia.

[tunnour]

salut

est ce que je peux appliqué l'algo en profondeur à un graphe orienté?

[fatal_error]

oui.
kikoolol10caracterelol

[tunnour]

dans graphe orienté, lalgo de parcours en largeur ou en profondeur ne permet pas de déterminer touts les chemins

[fatal_error]

Je veux trouver tous les chemins d'un point A à un point B .

Les deux que t'as cités le permettent très bien.

Si tu veux trouver tous les chemins d'un point QUELCONQUE A vers un autre point QUELCONQUE B, alors tu peux être naïf :
Tu applique l'algo largeur /profondeur pour chaque paire de noeud

ya mieux, mais en même temps t'es pas super précis dans ce que tu recherches...

[tunnour]

Les deux que t'as cités le permettent très bien.

Si tu veux trouver tous les chemins d'un point QUELCONQUE A vers un autre point QUELCONQUE B, alors tu peux être naïf :
Tu applique l'algo largeur /profondeur pour chaque paire de noeud

ya mieux, mais en même temps t'es pas super précis dans ce que tu recherches...

[img][IMG]http://img31.imageshack.us/img31/1585/dddkc.th.png[/img][/IMG]
voile le graphe de mon études
merci bien de m'expliquer comment je peux déterminer tous le chemins d'un noeud vers un autre

[fatal_error]

si c'est ca ton graphe, tu peux y faire a la main!

Tu cherches l'exhaustivité des chemins.
Si jamais tu cherches une méthode automatique, j'opterais pour appliquer un algo, mettons profondeur, sur chaque paire de noeud.

Eventuellement, on peut ameliorer en faisant un peu de backtracking. ( = lorsqu'on a un chemin, on cherche le noeud parent de notre noeud initial et on enleve ce chemin de la liste du noeud parent a chercher.
Ca revient a, pour un noeud qui a tout exploré, le marquer comme exploré. De tel manière qu'en prenant un autre noeud comme Root, ben on reparcourt pas ce noeud exploré.

Il existe certainement un algo tout beau tout pres, mais je ne le connais pas.

Bon à défaut de suer (cqui vaut pas le coup ici je pense), algo de pronfondeur+appliquer sur chaque paire de noeud!

[tunnour]

si c'est ca ton graphe, tu peux y faire a la main!

Tu cherches l'exhaustivité des chemins.
Si jamais tu cherches une méthode automatique, j'opterais pour appliquer un algo, mettons profondeur, sur chaque paire de noeud.

Eventuellement, on peut ameliorer en faisant un peu de backtracking. ( = lorsqu'on a un chemin, on cherche le noeud parent de notre noeud initial et on enleve ce chemin de la liste du noeud parent a chercher.
Ca revient a, pour un noeud qui a tout exploré, le marquer comme exploré. De tel manière qu'en prenant un autre noeud comme Root, ben on reparcourt pas ce noeud exploré.

Il existe certainement un algo tout beau tout pres, mais je ne le connais pas.

Bon à défaut de suer (cqui vaut pas le coup ici je pense), algo de pronfondeur+appliquer sur chaque paire de noeud!

LE problème ici est qu'on a doit utilisé des noeud plus q'une fois, par exemple si en veut passer du us occupation vers us victims, on dois passé 2 fois par Radical iraq, donc je peux plus éliminer un neud qui a été déjà utilisé

[fatal_error]

je dois pas comprendre ce que signifie tes symboles +,++,+++,- et --.
Je pensais qu'ils signifaient le cout de transition entre deux noeuds cad (+1,+2,+3,-1,-2).
Apparemment, ils semblent indiquer par combien de fois il faut passer par un noeud???

Peux-tu expliquer un peu plus stp?

[tunnour]

chaque - correspond à -1 et chaque + correspond à +1
les - et les + désignent le poid de chaque arcs

[fatal_error]

LE problème ici est qu'on a doit utilisé des noeud plus q'une fois, par exemple si en veut passer du us occupation vers us victims, on dois passé 2 fois par Radical iraq, donc je peux plus éliminer un neud qui a été déjà utilisé

Je ne comprends pas non plus pourquoi on doit passer 2 fois par Radical Iraq :
US Occupation>IraqiVictims>Radical Iraq>usVictims
US Occupation>Facilities>Radical Irq>usVictims
sont les deux seuls chemins. Pourtant aucun ne passe deux fois par Radical Iraq.

Si tu désires par exemple qu'en milieu de chemin tu te tapes un cycle, c'est a dire que tu passes deux fois par le même noeud, avant de sortir de la boucle, il suffit de trouver les cycles, puis d'appliquer l'algo de profondeur.

Celui-ci te donne un chemin sans cycle. Il suffit de remplacer un noeud par un cycle auquel il appartient, ou bien deux, etc...

Si ta question était je veux tous les chemins de US Occupation a Us Victims sans cycles,
pas de soucis le noeud Radical Iraq, quand il est parcouru, est supprimé des noeuds possibles, mais QUE pour le chemin en cours. Des que tu tentes un autre itinéraire, il sera de nouveau disponible.

[tunnour]

Je ne comprends pas non plus pourquoi on doit passer 2 fois par Radical Iraq :
US Occupation>IraqiVictims>Radical Iraq>usVictims
US Occupation>Facilities>Radical Irq>usVictims
sont les deux seuls chemins. Pourtant aucun ne passe deux fois par Radical Iraq.

Si tu désires par exemple qu'en milieu de chemin tu te tapes un cycle, c'est a dire que tu passes deux fois par le même noeud, avant de sortir de la boucle, il suffit de trouver les cycles, puis d'appliquer l'algo de profondeur.

Celui-ci te donne un chemin sans cycle. Il suffit de remplacer un noeud par un cycle auquel il appartient, ou bien deux, etc...

Si ta question était je veux tous les chemins de US Occupation a Us Victims sans cycles,
pas de soucis le noeud Radical Iraq, quand il est parcouru, est supprimé des noeuds possibles, mais QUE pour le chemin en cours. Des que tu tentes un autre itinéraire, il sera de nouveau disponible.

salut
vous pouvez me donnez une tentative d'un algorithme qui résoudre ce problème,

merci bien

[Ben314]

Salut,
Ce que tu cherche à calculer ne me semble toujours pas clair du tout :
Ton graphe contient des cycles dont la somme des poids n'est pas nulle (par exemple Facilities->Radical Irac->Facilities) ce qui fait qu'il existe par exemple une infinité de chemin entre certains points...
Tu peut imposer aux chemins d'être injectif, c'est à dire de ne pas passer deux fois par le même sommet sauf que :
1) Je ne vois pas quel argument "non mathématique" te permet de faire une telle hypothèse
2) Cela pose encore un problème pour savoir si parmi les deux chemins :
US Occupation>IraqiVictims>Radical Iraq>usVictims
US Occupation>Facilities>Radical Irq>usVictims
de US Occupation à usVictim, est ce que tu prend les deux ou un seul des deux (et dans ce cas lequel) ?

P.S. Intuitivement, je ne vois pas ce que tu cherche à "calculer" dans ton graphe. Il faut faire extrèmement attention que on applique des maths à un autre domaine à ne pas faire des calculs "mathématiquement justes" mais qui dans le contexte sont du.... n'importe quoi.