Probleme de recherche de tous les chemins en théorie des graphes

[Kvas²]

Bonjour à tous!

je rencontre un problème pour implémenter une mesure permettant de calculer le nombre de chemins de longueur l entre deux nœuds donnés x et y dans un graphe non orienté.


Merci d'avance!

[fatal_error]

slt,

tu peux construire une matrice d'adjacence et l'elever a la puissance l, et a la ligne x, sil y a 1 dans la case (x,y) cest que il existe un chemin de longueur l de x a y

[Cliffe]

Il veut le nombre de chemin.

DFS

[Kvas²]

Merci! je tiens à préciser (:ptdr: ) tout d'abord que je suis une fille! :marteau:

Comme l'a suggéré fatal_error, c'est une bonne idée seulement cette méthode ne me permet pas de calculer le nombre de chemins de longueur quelconque entre deux nœuds (x et y) . Bien entendu, pour mon application, il ne serait pas intéressant d'avoir des chemins non simples (pas de répétitions de nœuds).

Comme je ne connais pas encore bien utiliser les outils de dessins de graphe, je ne peux pas vous montrer par une illustration la différence entre ce que l'algorithme DFS produit et ce à quoi je m'attends.

La solution que je propose est très lourde. Une amélioration de son temps d’exécution me sera la bienvenue. Mon approche consiste à construire un arbre de racine le nœud de départ. Les sommets du niveau 1 de l'arbre représentant les voisins du nœud de départ x et ceux du niveau i+1 les voisins des nœuds du niveau i qui n'ont pas encore été utilisé sur la branche considérée (sur une branche, il ne dois apparaître un nœud qu'une seule fois tout au plus).

[fatal_error]

re,

tjs avec mes matrices d'adjence.
Comme tu veux pas compter les chemins avec les boucles, il suffit dignorer les coeffs sur la diago.
si 1 represente la liaison entre deux noeuds, alors
il suffit de considerer la matrice M, dont la premiere ligne v correspond a ta racine, et la derniere colonne ta destination.

Du coup, si on nomme v la premiere ligne de M, on a
v qui donne un vecteur de 0 ou 1 (representant les liaisons de la racine aux divers noeuds), et la derniere composante de v le nombre de chemins vers la destination.

De fait, le nombre de chemins devrait etre donne par
nbChemins = somme(i=1 a n) M^i (premiere ligne, dernierElement)

Cquil faut noter, c'est qu'il faut pas prendre en compte dans le calcul de M^i les coeffs diagonaux de M^k qui representent des boucles (genre considerer que ca vaut 0)

spas teste, mais ca me semble legit

[Dlzlogic]

Bonjour,
Je voudrais expliquer la méthode que j'utilise pour gérer et utiliser les graphes.
D'abord j'ai une structure de description de noeud.
On y trouve son identifiant et la liste des noeuds immédiats avec éventuellement des indications supplémentaires.
Il est très facile de parcourir une telle liste pour faire les opérations nécessaires.
Par exemple la recherche d'itinéraire.

[Cliffe]

fatal_error : à quoi correspond 'n' pour toi ?

[fatal_error]

au nombre de noeuds dans le graphe

[Cliffe]

manque pas un 'l' dans ta formule ?

[Cliffe]

Pk tu écris "(premiere ligne, dernierElement)" et pas (1, n) ?

[fatal_error]

parce que j'aime pas rentrer trop dans les details, 0,1, n-1, n...
n me semble assez explicite pour deviner le nombre de noeuds, mais specifie dans les parentheses, ca me parait apporter le detail n et non n-1, et j'ai pas envie de m'embeter avec ce genre de subtilites

[Cliffe]

C'est un forum de math quand même ... :marteau:

[fatal_error]

S'il y a des questions parce que je suis trop flou, j'y repondrai. Maintenant, si tu as du temps pour ces details, tu peux egalement le consacrer a la question de notre chere KVas2

PS: C'est un forum de math quand même ...

le but c'est un peu de pondre un algo, certains comptent a zero, les matheux...a 1.

[Cliffe]

J'essaye de comprendre ce que tu as fait. Je vois pas pk il n'y a pas de 'l' dans ta formule ?

Tu as tester si sa fonctionne sur un ex. simple ?

[Cliffe]

C'est un exo qui m'intéresse.

Si on oriente le graphe à partir de r (racine) et qu'on calcul la puissance l-ième sur la nouvelle matrice d'adjacence, sa fonctionnerait pas ?

[fatal_error]

J'essaye de comprendre ce que tu as fait. Je vois pas pk il n'y a pas de 'l' dans ta formule ?

pourquoi devrait-il y avoir une lettre qui sort de nulle part?

Tu as tester si sa fonctionne sur un ex. simple ?

non

Si on oriente le graphe à partir de r (racine) et qu'on calcul la puissance l-ième sur la nouvelle matrice d'adjacence, sa fonctionnerait pas ?

peut-être bien...

[Kvas²]

Merci, mais orienter le graphe à partir d'une racine r revient à construire une sorte d'arbre et donc une structure hiérarchique.

[Dlzlogic]

Merci, mais orienté le graphe à partir d'une racine r revient à construire une sorte d'arbre et donc une structure hiérarchique.

Par forcément.
Le prends l'exemple d'un centre de secours. La racine sera toujours la caserne, et il y a en général plusieurs chemins qui mènent au lieu de l'incendie.

[Kvas²]

Par forcément.
Le prends l'exemple d'un centre de secours. La racine sera toujours la caserne, et il y a en général plusieurs chemins qui mènent au lieu de l'incendie.

je vois ce que tu veux dire! En fait on dit la même chose!

suppose que j'ai le graphe suivant
1 -- 2
| fgf |
3 -- 4

en construisant l'arbre à partir du noeud 1 j'obtiens ceci:

ryy-- 2 -- 4 -- 3
1
ryy-- 3 -- 4 -- 2

il y a bien deux chemins qui mènent au nœud 3 partant de 1, l'un est de longueur 1 (1-3) et l'autre de longueur 3 (1-2-4-3). C'est ce que tu disais n'est ce pas ?

[Dlzlogic]

Oui, c'est vrai.
Mais il faut reconnaitre que la première organisation qui comporte 4 éléments est tout de même plus économique que la seconde qui en comporte 7.
L'intérêt des graphes est justement de trouver tout de suite le ou les segments qui partent du noeud où on se trouve.
Quand on a quelques centaines de noeuds, voire quelques milliers, ce n'est plus tout à fait équivalent.
Autre avantage, la mise à jour, création, modification est immédiate.