Ayuda con mi proyecto de grafos

[JorgeKun]

Veran tengo que hacer un proyecto de un tipo GPS usando grafos, mi problema radica en que no se como declarar un grafo que tendra 45 nodos y sera estatico, el resultado de mi programa espero que sea algo como:
Si usted parte de.... pasara por ...,...,...,..., ese es el camino mas optimo y el peso es x.

Utilizando el algoritmo de Dijkstra, pero llevo un par de dias teniendo problemas declarando el grafo, ahora intento hacerlo usando una lista de adyacencia pero es mucho codigo declarando los 45 nodos :/, espero me puedan hechar una mano.

[Acermax]

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.

[pucheto]

... un par de dias teniendo problemas declarando el grafo, ahora intento hacerlo usando una lista de adyacencia pero es mucho codigo declarando los 45 nodos :/

Es el laburo minimo q vas a tener q hacer para 45 nodos al azar... Son 45 nodos, vas a tener q escribir los 45... Al menos q cumplan alguna propiedad... Es mas rapido escribirlo q consultarlo en un foro ( chiste, no lo tomes a mal )..

Y Acermax, como propones representarlo con vectores?

[Acermax]

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.

[pucheto]

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.

Eso es una forma de representar un grafo... Es una matriz de adyacencias... Y Djkstra lo tiene que aplicar igual... La distancia de un nodo a otro, y su camino, lo tiene q calcular si o si...

[Acermax]

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.

[ghastlyX]

Discrepo. Yo considero que para este caso es mejor una lista de adyacencia. El código no se complica para nada y en caso general es más eficiente que con una matriz de adyacencia para hacer un Dijkstra (pese a que con 45 nodos no se notará la mejoría).

[Akai]

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.

[ghastlyX]

Si se quiere conservar un camino mínimo usando Dijkstra, una manera sencilla de hacerlo es guardar para cada nodo su antecesor, de manera que cada vez que se relaja el coste mínimo de un nodo, se pone como padre o antecesor el nodo origen de la arista (o arco) empleada.

Como he puesto, con esto se guarda un camino mínimo para cada nodo, no todos en caso de que haya más de un camino mínimo que acabe en un nodo.

[Maurice_Lupin]

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í