Discussion :

[Alikendarfen]

Bonjour,

Je cherche à trouver le (ou l'un des) plus court(s) chemin(s) reliant tous les sommets d'un graphe (non orienté).

Il n'y a pas de point de départ ou d'arrivée, il faut simplement trouver le plus court chemin passant par tous les sommets (et en ne passant qu'une seule fois par un sommet donné).

Dans mon cas, tout sommet est relié à chaque autre par un arc.

A priori, il suffit d'ajouter un sommet factice (relié à chaque autre par un arc de poids nul) pour se ramener à un voyageur de commerce.

Mais est-ce bien le cas ? Ou bien y a-t-il une autre approche ici ?


PS : j'ai bien entendu effectué une recherche avant ce post... mais beaucoup d'entrées trouvées sans avoir de réponse directe à cette question...

[Graffito]

il faut simplement trouver le plus court chemin passant par tous les sommets (et en ne passant qu'une seule fois par un sommet donné).

Avec un graphe composé de 3 triangles avec un sommet commun (genre symbole nucléaire : http://1.bp.blogspot.com/_dM_o3m0Fids/TObRwVurDgI/AAAAAAAAAsk/3jx_K36xpS0/s400/nucleaire.jpg), on ne peut pas parcourir tout le graphe sans passer plusieurs fois par le centre.

[Alikendarfen]

Avec un graphe composé de 3 triangles avec un sommet commun (genre symbole nucléaire : http://1.bp.blogspot.com/_dM_o3m0Fids/TObRwVurDgI/AAAAAAAAAsk/3jx_K36xpS0/s400/nucleaire.jpg), on ne peut pas parcourir tout le graphe sans passer plusieurs fois par le centre.

Oui Graffito, mais j'ai bien précisé : "Dans mon cas, tout sommet est relié à chaque autre par un arc."

[pseudocode]

A priori, il suffit d'ajouter un sommet factice (relié à chaque autre par un arc de poids nul) pour se ramener à un voyageur de commerce.

De mon point, c'est déjà un pb de voyageur de commerce avec des routes entre toutes les villes.

D'une manière plus générale, il s'agit de trouver le plus court chemin hamiltonien dans un graphe complet.

[Alikendarfen]

De mon point, c'est déjà un pb de voyageur de commerce avec des routes entre toutes les villes.

D'une manière plus générale, il s'agit de trouver le plus court chemin hamiltonien dans un graphe complet.

Oui... donc ça confirme c'est un voyageur de commerce ou similaire ? Pas de simplification possible ?

[pseudocode]

Oui... donc ça confirme c'est un voyageur de commerce ou similaire ? Pas de simplification possible ?

C'est un problème NP-Complet, et je ne pense pas qu'être dans un graphe complet améliore les choses.

[Alikendarfen]

Oui.

Pour info, le graphe est complet parce que je n'ai pas de graphe à la base.

Si on reformule le problème en prenant une illustration :

On a N villes.

Quel est le chemin qui passe par toutes les villes et seulement une seule fois par ville et qui soit le plus court possible (et sachant que la ville de départ n'est pas fixée et qu'on ne cherche pas un circuit) ?