Para resolver el problema del viajante te sería mas optimo lo siguiente :

1) Almacenar pesos de los caminos entre nodos ( ciudades ) en una matriz, y una matriz de adyacencias , y aplicar el algoritmo de kruskal y haciendole unas pequeñas modificaciones ( ya que kruskal realmente da el arbol generador minimo, ergo no volverías nunca a la ciudad ), consegurías un camino, pero no te va a garantizar que este sea minimo.

2) La solución existente que hay del problema, es NP-COMPLETO ( http://es.wikipedia.org/wiki/NP-completo ), vamos, que la única manera de hacerlo sin debanarse mucho los sesos es hacer fuerza bruta sobre el grafo, probando TODOS los caminos posibles