elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Curso de javascript por TickTack


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Ayuda con mi proyecto de grafos
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] 2 Ir Abajo Respuesta Imprimir
Autor Tema: Ayuda con mi proyecto de grafos  (Leído 12,795 veces)
JorgeKun

Desconectado Desconectado

Mensajes: 7


Ver Perfil
Ayuda con mi proyecto de grafos
« en: 28 Mayo 2011, 20:21 pm »

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.


En línea

Acermax

Desconectado Desconectado

Mensajes: 55


Ver Perfil
Re: Ayuda con mi proyecto de grafos
« Respuesta #1 en: 29 Mayo 2011, 03:43 am »

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.


En línea

pucheto

Desconectado Desconectado

Mensajes: 215


Ver Perfil
Re: Ayuda con mi proyecto de grafos
« Respuesta #2 en: 29 Mayo 2011, 15:47 pm »

... 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 :P ( chiste, no lo tomes a mal )..

Y Acermax, como propones representarlo con vectores?
En línea

Acermax

Desconectado Desconectado

Mensajes: 55


Ver Perfil
Re: Ayuda con mi proyecto de grafos
« Respuesta #3 en: 29 Mayo 2011, 15:55 pm »

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.
En línea

pucheto

Desconectado Desconectado

Mensajes: 215


Ver Perfil
Re: Ayuda con mi proyecto de grafos
« Respuesta #4 en: 29 Mayo 2011, 16:18 pm »

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...
En línea

Acermax

Desconectado Desconectado

Mensajes: 55


Ver Perfil
Re: Ayuda con mi proyecto de grafos
« Respuesta #5 en: 29 Mayo 2011, 16:27 pm »

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.
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Ayuda con mi proyecto de grafos
« Respuesta #6 en: 29 Mayo 2011, 17:55 pm »

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).
En línea

Akai


Desconectado Desconectado

Mensajes: 823



Ver Perfil
Re: Ayuda con mi proyecto de grafos
« Respuesta #7 en: 29 Mayo 2011, 18:10 pm »

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.
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Ayuda con mi proyecto de grafos
« Respuesta #8 en: 29 Mayo 2011, 18:24 pm »

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.
En línea

Maurice_Lupin


Desconectado Desconectado

Mensajes: 356

GPS


Ver Perfil WWW
Re: Ayuda con mi proyecto de grafos
« Respuesta #9 en: 29 Mayo 2011, 19:31 pm »

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í  :-X
En línea

Un error se comete al equivocarse.
Páginas: [1] 2 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Ayuda con grafos en c
Programación C/C++
marrison 9 5,244 Último mensaje 2 Enero 2015, 14:29 pm
por Yoel Alejandro
ayuda urgente laberinto con grafos
Programación C/C++
blaaaack 0 3,702 Último mensaje 20 Junio 2017, 02:33 am
por blaaaack
Proyecto de Estructura de datos.... GRAFOS!!! :c
Programación C/C++
axel19 3 2,239 Último mensaje 29 Mayo 2018, 20:17 pm
por Serapis
ayuda con recorrido de grafos en amplitud y profundidad
Programación C/C++
Beginner Web 0 1,367 Último mensaje 10 Noviembre 2018, 17:17 pm
por Beginner Web
Ayuda Con Este ERROR, GRAFOS
Programación General
verakra 1 2,442 Último mensaje 29 Febrero 2020, 21:55 pm
por K-YreX
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines