Discussion :

[lechewal]

Bonjour !

ma question est assez simple mais je ne trouve pas de reponse clair sur le web..

Peut on appliquer les algos de recherche du plus court chemin (dijktra, bellman) avec des graphes non orientés ?

Merci

[Jedai]

Bien sûr, puisqu'un graphe non-orienté est strictement équivalent à un graphe orienté où chaque flèche a sa réciproque...

--
Jedaï

[lechewal]

merci !!

Mais a ton avis, c'est plus efficace de dupliquer les arcs dans la representation en memoire et utilser le meme algo ensuite

ou bien de faire un algo adapté a chacun des representation ?

a+

[benratti]

Si tu as bien fait ton boulot, il n'y a rien a faire. Les algos de chemins le plus court fon appel a un fonction qui renvoie la liste des successeurs d'un sommet ( tous les arcs sortant ), et bien pour un graphe non-oriente, il renverra toutes les aretes ayant comme extremite le sommet considere...

T'as normalement qu'a adapter ta fonction successeur en fonction du type de graphe mais ca devrait etre fait dans toute bonne implementation de graphe.

Donc ma reponse est ni l'un ni l'autre, il n'y a normalement pas de difference.

[lechewal]

Hum, j'ai du mal faire mon boulot

J'y avait pensé mais j'avais trouvé que d'appeller une fonction qui renvoie une liste de successeur est plus lourd qu'une simple boucle..

mais bon, je vais y reflechir

a+

[benratti]

J'y avait pensé mais j'avais trouvé que d'appeller une fonction qui renvoie une liste de successeur est plus lourd qu'une simple boucle..

Plus lourd, je ne pense pas. Perso, je trouve ca plus lourd de devoir reecrire une boucle parcourant tous les successeurs dans chaque algo. De plus, l'appel d'une fonction est dans de nombreux langages tres peu couteuse. Et de toute facon, c'est pas a ce niveau qu'il faut faire les optimisations ( ou alors c'est que tu as deja tout optimise ).

[lechewal]

Ok, merci pour votre reponse !

Mais n'est ce pas plus efficace lorsque l'on recoit en entrée un graphe non orienté de le representer en memoire en doublant les arcs ?

Car si on garde une representation ou l'on garde qu'un seul des arcs, touver les successeurs devient très couteux, meme si on a une fonction qui le fait non ?

[benratti]

Il me semble que je ne comprends pas tout a ton probleme. A l'origine de ton message, tu demandais :

Peut on appliquer les algos de recherche du plus court chemin (dijktra, bellman) avec des graphes non orientés ?

On te repondais que oui, il n'y avait pas de probleme. Car :
1/ il est possible de creer un graphe oriente equivalent en doublant toutes les fleches de ton graphe et en les inversant
2/ les algo de plus court chemin ne prennent pas en compte le fait que ton graphe soit oriente ou non. Dans les deux cas tu as une fonction successeurs.

J'ai l'impression ( je me trompe peux-etre ) que tu veux melanger les deux points. En fait, les deux sont des arguments pour repondre "oui" a ta question. De la deux choix sont possibles : soit tu decides de creer le graphe oriente equivalent, soit tu decides de ne rien faire car ton implementation le permet. Mais c'est deux choses plus ou moins differentes.

Pour repondre a ta question sur l'efficacite, je dirais que ca depends exclusivement de ton choix d'implementation de ton graphe en memoire.

Mais dans la plupart des representations que je connaisse ( matrice d'incidence, matrice d'adjacence, etc ... ) il est tres facile de recuperer les successeurs ( ca se fait generalement en un temps lineaire ) que ce soit des graphes oriente ou non. Si tu prends par exemple la matrice d'incidence, tu n'as pas de difference de representation. Il y aura simplement une legere redondance dans l'information qui est contenu, mais tu auras du mal a l'eviter.

Bref, si tu separes bien l'implementation du traitement, tu n'as meme pas a se poser cette question.
Pour finir, je vais repondre a ta question suivante :

Car si on garde une representation ou l'on garde qu'un seul des arcs, touver les successeurs devient très couteux, meme si on a une fonction qui le fait non ?

Quand tu me dis que tu gardes qu'un seul arc, ca signifie quoi ?? Car ca veut dire que tu stockes des arcs et non des aretes ( j'appele arete les "arcs" des graphes non-oriente )

[lechewal]

Bref, si tu separes bien l'implementation du traitement, tu n'as meme pas a se poser cette question.
Pour finir, je vais repondre a ta question suivante :

Car si on garde une representation ou l'on garde qu'un seul des arcs, touver les successeurs devient très couteux, meme si on a une fonction qui le fait non ?

Quand tu me dis que tu gardes qu'un seul arc, ca signifie quoi ?? Car ca veut dire que tu stockes des arcs et non des aretes ( j'appele arete les "arcs" des graphes non-oriente )

Par exemple, en cas de representation par matrice, on ne stocke que la matrice triangulaire.

Mais après reflexion, je vais, en memoire, faire la redondance.

Merci en tout cas !
a+

[benratti]

Par exemple, en cas de representation par matrice, on ne stocke que la matrice triangulaire.

Dans le cas de la matrice d'adjacence, tu peux stocker uniquement la matrice triangulaire pour les graphes non-orientes, mais la methode d'acces au successeurs ne s'en trouve pas beaucoup plus longue. au final tu vas parcourir tous les sommets et voir si c'est un successeur ( au passage, il y a plus efficace avec par exemple la matrice d'incidence, cf ce sujet ).