Discussion :

[DamienDLR]

Bonjour à tous et toutes,
je suis en stage de fin d'étude et je recherche un algorithme de graphe me permettant de résoudre le problème cité en dessous.

Je possède un nombre d'éléments (sommets) variables n et je souhaite réaliser un tracer unique, chaque élément doit être connecté au maximum à deux autres (sauf départ et arrivée). Et ce en ayant le chemin global le plus court. Jusqu'ici c'est simple.

Le problème est qu'il n'existe pas d’arêtes, c'est moi qui les traces et qui leur donne un poids (distance séparant les deux éléments). Le graphe n'est pas orienté.
Et je n'arrive pas à trouver mon bonheur dans les algorithmes de résolution classiques (Dijkstra, Dantzig...).

Merci à tous et toutes.

Damien

[Prof]

Bonjour.

Ce problème semble être celui du " voyageur de commerce ".

C'est un problème bien connu ( voir Google ).

Malheureusement, et là je cite Wikioedia :

Il s'agit d'un problème d'optimisation pour lequel on ne connait pas d'algorithme permettant de trouver une solution exacte en un temps polynomial. De plus, la version décisionnelle de l'énoncé (pour une distance D, existe-t-il un chemin plus court que D passant par toutes les villes ?) est connue comme étant un problème NP-complet.

[DamienDLR]

Merci pour votre réponse.

Je me doutais que cela serai difficile à trouver mais je pense pouvoir le réaliser.
Affaire à suivre donc et merci encore pour ta réponse Prof.