Y para que quieres usar un grafo para eso?
Son ganas de complicarte la vida, cuando lo más simple es usar vectores y se soluciona tu problema.

Pues no es dificil, sabiendo que son 45 nodos, puedes hacer una matriz de 45x45 que indique la distancia de un nodo a otro, con eso ya lo tienes todo hecho, reordenas el vector según el algoritmo, y lo vas realizando.

Claro, pero no es necesario crear una clase "Grafo" ni mucho menos. El algoritmo se representa mediante un grafo matemáticamente, pero a la hora de implementarlo, y más sabiendo que el tamaño es constante, una matriz es lo mejor.

Has pensado en NO declararlo estático y que cargue en la ejecución del programa? Pon los datos en un fichero y léelos al iniciar la ejecución del programa para construir el grafo. Esto en mi opinión te va a simplificar muchísimo el código resultante.

Por otro lado, lo que tu buscas, a parte del camino más corto, es reconstrucción de caminos. Dado que estás usando Dijkstra para obtener el camino más corto entre un nodo A y otro B y no todos los caminos más cortos, una opción sería almacenar los nodos que decides que forman parte de tu camino más corto en una lista o algo por el estilo. Con Floyid-Warshall si conozco la manera de hacerlo, pero con dijkstra no lo he implementado nunca.

No entiendo mucho de grafos, me imagino que podrías crear un archivo con las coordenadas de cada punto, leerlos desde tu programa y generar combinaciones con esos puntos.
Almacenas en un vector cada combinación o trazado, determinas distancia total para cada combinación, al final comparas las distancias y eliges la menor.
Espero haberte entendido, me recuerda un problema para implementa una de Red de computadoras que esta en este foro. Lo resolví en java, así que está prohibido mostrar código aquí