Sé que resolver un TSP requiere considerar todos los ciclos posibles en el grafo, y que un algoritmo codicioso del vecino más cercano no siempre produce el camino más corto. He encontrado este respuesta que da un contraejemplo para tal algoritmo codicioso, pero sólo considera empezar desde un vértice específico (A). Mi pregunta es, si aplicamos este algoritmo codicioso n veces a partir de cada uno de los n vértice, ¿por qué no iba a producir un camino corto óptimo? Aún no he encontrado ningún contraejemplo.
El TSP suele referirse a un viaje de ida y vuelta. No hay solución de ida y vuelta de peso $8$ en este gráfico (ya que sólo hay $7$ bordes de peso $1$ ).
