Gracias Nelson.
Como comentaba, no se traba de encontrar el camino mínimo utilizando algoritmos conocidos, como el de Dijkstra.
Lo que pasa es que no daba con el nombre del problema, que seguro que estaba ya resuelto. Pero ya lo he encontrado. Lo que necesitaba es una variante del problema del viajante (TSP), en el que se debe recorrer un conjunto de nodos y obtener el camino óptimo. (
http://es.wikipedia.org/wiki/Problema_del_viajante)
El proceso, por tanto, tratará de encontrar el circuito hamiltoniano con suma de etiquetas (distancias) mínima.
Un saludo