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.
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.
Cita de: JorgeKun en 28 Mayo 2011, 20:21 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?
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.
Cita de: Acermax 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.
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...
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.
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).
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.
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.
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
Sin ánimo de ofender, Maurice_Lupin:
Si no entiendes de grafos, no líes más la perdiz, en este caso los grafos abstraen todo el trabajo de las coordenadas en simples relaciones entre puntos. No intentemos reinventar la rueda, este caso no lo necesita.
entiendo su punto pero vera en un proyecto para la facultad donde se nos pidio emplear grafos para dicho proposito y si he estado tratando con una rchivo pero me da problemas , sigo revisando el codigo.
Creo que optare por hacer la matriz de adyacencia de 45x45, aunque espero terminar...es para mañana :-X
Gracias por su tiempo :-*
Pues si me ofendiste y no creo haber reinventado nada.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <conio.h>
#define MaxNodos 10
typedef struct nodo_ {
int etiqueta;
float peso;
struct nodo_ *sig;
}Tnodo;
/** variables globales */
Tnodo *Lista[MaxNodos]; //lista de adyacencia
int marca[MaxNodos]; //visitados
int predecesores[MaxNodos]; //ruta
float d[MaxNodos]; // distancia - peso
int Num_Vertices; //numero de vertices
int tipo; //1 no dirigido, 0 dirigido
/** ------------------ */
/* Inicializa la lista de adyacencia a NULL */
void init() {
int i;
for (i = 0; i < MaxNodos; i++)
Lista[i] = NULL;
}
/* Muestra la lista de adyacencia (un simple debug) */
void mostrar_lista_adyacencia () {
Tnodo *q;
int i;
for (i = 0; i < Num_Vertices; i++) {
if (Lista[i] != NULL) {
q = Lista[i];
printf ("vertice %d: ", i);
while (q) {
printf ("%d ", q->etiqueta);
q = q->sig;
}
printf("\n");
}
}
}
/* Inserta los vertices en la lista de adyacencia */
void inserta (int Vorigen, int Vfinal, float peso) {
Tnodo *q;
q = (Tnodo*) malloc (sizeof(Tnodo) * 1);
if (!q) return; //hubo un error
q->etiqueta = Vfinal-1;
q->peso = peso;
q->sig = NULL;
if (Lista[Vorigen-1] != NULL)
q->sig = Lista[Vorigen-1];
Lista[Vorigen-1] = q;
}
/* Libera la lista de adyacencia */
void liberar_lista (void) {
Tnodo *q;
int i;
for (i = 0; i < Num_Vertices; i++) {
if (Lista[i] != NULL) {
while (Lista[i] != NULL) {
q = Lista[i];
Lista[i] = Lista[i]->sig;
free(q);
}
} //--fin si (no necesarias las llaves)
} //--fin for (no necesaria las llaves)
}
/* Carga el grafo desde un fichero */
void cargar_grafo (char *fn) {
FILE *fp;
int v_in, v_fn; //vertice inicial y final
float peso;
if ((fp = fopen (fn, "r")) == NULL) {
printf ("El archivo %s no existe o no se puede abrir\n", fn);
getche();
exit(0);
}
fscanf (fp, "%d\n", &tipo); //tipo es una vble global
fscanf (fp, "%d\n", &Num_Vertices); //Num_Vertices es una vble global
while (!feof(fp)){
fscanf(fp, "%d %d %f\n", &v_in, &v_fn, &peso);
inserta(v_in, v_fn, peso);
inserta (v_fn, v_in, peso);
}
fclose (fp);
} // fin cargar_grafo
/* Retorna el peso de la arista que une dos nodos */
float return_peso (int origen, int destino) {
Tnodo *p;
int encontrado;
encontrado = 0;
p = Lista[origen];
while (p != NULL && !encontrado) {
if (p->etiqueta == destino)
encontrado = 1;
else
p = p->sig;
}
return p->peso;
}
int menor_valor() {
int i, verticeMenor;
float menor;
menor = INT_MAX;
for (i = 0; i < Num_Vertices; i++) {
if (marca[i] == 0 )
if (menor > d[i]) {
menor = d[i];
verticeMenor = i;
}
} // fin for
return verticeMenor;
}
/* Dijkstra */
void dijkstra (int origen, int destino)
{
int i, last, x;
Tnodo *p;
// inicializacion
for (i = 0; i < MaxNodos; i++) {
d[i] = INT_MAX; //"infinito"
marca[i] = 0;
predecesores[i] = -1;
}
// --
d[origen] = 0;
marca[origen] = 1;
last = origen;
while (marca[destino] == 0) { //hasta que no lleguemos al destino
p = Lista[last];
while (p != NULL){ //para todos los nodos adyacendes
if (marca[p->etiqueta] == 0) //si no ha sido visitado
if (d[p->etiqueta] > d[last] + return_peso(last, p->etiqueta))
{
d[p->etiqueta] = d[last] + return_peso(last, p->etiqueta);
predecesores[p->etiqueta] = last;
} // fin si
p = p->sig;
} // fin mientras
x = menor_valor();
marca[x] = 1;
last = x;
} // fin mientras
}
/* Imprime la ruta por pantalla */
void ImprimirCamino(int v) {
if (v != -1)
ImprimirCamino(predecesores[v]);
if (v != -1) //evitamos que se imprima el -1
printf("%d ",v+1);
}
/* Menu de opciones */
int menu() {
int opcion;
do {
printf ("\n[0] Salir\n");
printf ("[1] Calcular ruta\n");
printf ("Opcion: ");
scanf("%d", &opcion);
}while (opcion < 0 || opcion > 1);
return opcion;
}
/* Funcion principal */
int main () {
char file[25];
int origen, destino;
int salir = 0;
printf ("Cargar fichero?: ");
scanf("%s", file);
init();
cargar_grafo(file);
mostrar_lista_adyacencia(); //debug
do {
switch(menu()) {
case 0:
salir = 1;
break;
case 1:
do {
printf ("Vertice origen: "); scanf("%d", &origen);
printf ("Vertice destino: "); scanf("%d", &destino);
if (origen < 1 || origen > MaxNodos || destino < 1 || destino > MaxNodos)
printf ("Error: El rango tiene que estar comprendido entre 1 y %d\n", Num_Vertices);
}while (origen < 1 || origen > Num_Vertices || destino < 1 || destino > Num_Vertices);
dijkstra(origen-1, destino-1);
ImprimirCamino(destino-1);
break;
}; //final switch
}while(!salir);
liberar_lista();
}
Este codigo lo encontre navegando por ahiy empeze a basarme en el, veran funciona bien el problema es que no entiendo la manera en que me carga el archivo.
He estado experimentando un poco y al poner en el .txt "1 2 3" entiendo que lo toma como ,nodoOrigen,Costo,nodoDestino, pero aun asi me pierdo durante la ejecucion del codigo y no me entrega las distancias :/, espero me puedan ayudar a entender como abre el archivo porfavor y como lo trabaja, ya que ese es mi problema, gracias de antemano :-*
El archivo debería ser algo así por la forma en la cual lo estás leyendo:
1
5
0 1 15
3 4 20
2 0 4
4 2 7
siguiendo el patrón:
tipo
numero de vertices
arista
arista
arista
...
no estoy demasiado seguro que estuvieses siguiendo ese patrón.
Tienes razon yo seguia un patron Origen---Costo de arista----Destino,
pero solo una duda, disculpa si sueno muy noob, pero al llegar a las aristas en tu ejemplo como esta declarado, ejemplo:
0 1 15
el primero y ultimo son los nodos y el de enmedio es el costo? o estoy entendiendo mal? :-X
Eso está en tu propio código. Yo únicamente me he dedicado a crear un ejemplo siguiendo el patron de lectura:
void cargar_grafo (char *fn) {
fscanf (fp, "%d\n", &tipo); //tipo es una vble global
fscanf (fp, "%d\n", &Num_Vertices); //Num_Vertices es una vble global
while (!feof(fp)){
fscanf(fp, "%d %d %f\n", &v_in, &v_fn, &peso);
inserta(v_in, v_fn, peso);
inserta (v_fn, v_in, peso);
}
} // fin cargar_grafo
Primero que nada muchas gracias ya entendi perfectamente mi error, y tambien que el proyecto es poco eficiente pero en fin es tarea xD.
Segundo esa parte del archivo no es codigo mio por eso no entendia que hacer pero gracias a su ayuda ya lo entendi!!!
Muchas gracias!!, espero serle util a alguien tambien algun dia ;)
Mas tarde posetare el resultado final y ya mañana les dire que tal me fue presentadolo ante mi clase
Bueno el proyecto funciono muy bien :D, sin embargo me fue muy mal y tendre que presentarlo de nuevo :-( todo debido a que no imprimi el grafo en manera de grafica, yo lo imprimi en un simple listado :-X