Pour moi la différence est que le problème de plus court chemin peut se résoudre en temps polynomial (avec Dijkstra ou Bellman-Ford) alors que pour le problème voyageur du commerce on ne connait pas d'algo en temps polynomial pour le résoudre dans tous les cas.
Les problemes algorithmiques
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
« Je n’ai pas besoin de preuve. Les lois de la nature, contrairement aux lois de la grammaire, ne permettent aucune exception. »
D. Mendeleïev