Bonjour, avec l'algorithme de Dijkstra on peut trouver le chemin le plus
court sur un graphe, mais peut -on trouver le chemin le plus court passant
par tous les points ?
merci
----------------------------------------------------------------------------
--------------------- http://www.math93.com/ : Une histoire des mathématiques
----------------------------------------------------------------------------
-----------------------------------
Posted by: Jean-Loup GUILLAUME
Franck a écrit :
> Bonjour, avec l'algorithme de Dijkstra on peut trouver le chemin le plus
> court sur un graphe, mais peut -on trouver le chemin le plus court passant
> par tous les points ?
> merci
Si tu veux passer une fois et une seule par chaque sommet c'est un probleme de
chemin Hamiltonien et si un tel chemin existe alors c'est le plus court (n-1
aretes pour n sommets).
Mais c'est deja dans NP de faire ca, donc ton probleme me parait assez dur
(mais sans doute bien approximable).