Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: AlbertoBSD en 7 Agosto 2016, 02:20 am


Título: [Grafo] Base para el Algoritmo de Dijkstra
Publicado por: AlbertoBSD en 7 Agosto 2016, 02:20 am
Muy buen dia, les dejo la Base para realizar el algoritmo de dijkstra.

La imagen de ejemplo es la que esta en Wikipedia https://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra#/media/File:Dijkstra_Animation.gif

He aqui el código, el ejemplo que muestra que la ruta mas rápida de 1 a 5 tiene un peso total de 20

El código esta medianamente comentado y Imprime lo que esta haciendo en tiempo de ejecución.

Código
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4.  
  5. struct nodo	{
  6. 	int id;
  7. 	//Dato del Nodo
  8. 	//struct data *datos;	//En caso de apuntar a otro tipo de estrucutura	
  9. 	//Variables auxiliar para el Grafo
  10. 	int peso_actual;	//Contenedor del peso actual recorrido para llegar a este nodo
  11. 	struct nodo *mejor_ruta;	//Indice de la mejor ruta para llegar al nodo de la ultima busqueda -1 para datos no inicializados
  12. 	int visitado;	//Variable Entera de Visitado, almacena un numero Ramdon para deteminar si fue visitado o no por el proceso actual
  13. 	int out;
  14. 	int total;		//Total de vetices conectados a reste Nodo
  15. 	int *aristas;	//En caso de que existan distintos pesos para viajar al X vertice se ponen aqui
  16. 	struct nodo **vertices;	//Distintos vertices que se pueden alcanzar desde este Nodo
  17. 	//int *vertices; //En caso de aplicar un nodo por indices a un arreglo de nodos
  18. };
  19.  
  20. struct grafo	{
  21. 	int total;				// Total de nodos validos en el grafo
  22. 	int disponible;			// Total de espacios asignables en el grafo
  23. 	struct nodo **nodos;	//tabla de acceso rapido a X nodo
  24. };
  25.  
  26.  
  27. struct grafo *add(struct grafo *grafo_actual,int origen, int peso, int destino);
  28. void add_nodo(struct grafo *grafo_actual,int origen,int peso,int destino);
  29. int dijkstra(struct nodo *nodo_a,struct nodo *nodo_b);
  30. int menor_ruta(struct grafo *grafo_actual,int A,int B);
  31.  
  32. int main()	{
  33. 	struct grafo *grafo = NULL;
  34. /*
  35. struct grafo *add(struct grafo *grafo_actual,int origen, int peso, int destino);
  36. */
  37. 	grafo = add(grafo,1, 7,2);
  38. 	grafo = add(grafo,1, 9,3);
  39. 	grafo = add(grafo,1,14,6);
  40. 	grafo = add(grafo,6, 9,5);
  41. 	grafo = add(grafo,6, 2,3);
  42. 	grafo = add(grafo,3,11,4);
  43. 	grafo = add(grafo,3,10,2);
  44. 	grafo = add(grafo,2,15,4);
  45. 	grafo = add(grafo,4, 6,5);
  46. 	printf("Ruta %i\n",menor_ruta(grafo,1,5));
  47. 	return 0;
  48. }
  49.  
  50. int menor_ruta(struct grafo *grafo_actual,int A,int B)	{
  51. 	return dijkstra(grafo_actual->nodos[A-1],grafo_actual->nodos[B-1]);
  52. }
  53.  
  54. struct grafo *add(struct grafo *grafo_actual,int origen, int peso, int destino)	{
  55. 	/*
  56. 		Variables
  57. 	*/
  58. 	int mayor = destino;
  59. 	struct nodo **temp = NULL;
  60. 	/*
  61. 		Inicializamos el grafo en caso de que no exista
  62. 	*/
  63. 	if(grafo_actual == NULL)	{
  64. 		grafo_actual = calloc(1,sizeof(struct grafo));
  65. 	}
  66. 	/*
  67. 		Determinamos el indice mayor
  68. 	*/
  69. 	if(origen > destino)	{
  70. 		mayor = origen;
  71. 	}
  72. 	/*
  73. 		Evaluamos si tenemos espacio suficiente
  74. 	*/
  75. 	if(mayor > grafo_actual->disponible)	{
  76. 		/*
  77. 			En caso de no tener espacio suficiente lo reasignamos
  78. 		*/
  79. 		temp = calloc(mayor,sizeof(struct nodo*));
  80. 		if(temp)	{
  81. 			if(grafo_actual->nodos)	{
  82. 				memcpy(temp,grafo_actual->nodos,grafo_actual->disponible*sizeof(struct nodo*));
  83. 				free(grafo_actual->nodos);
  84. 				grafo_actual->nodos = NULL;
  85. 			}
  86. 			grafo_actual->nodos = temp;
  87. 			grafo_actual->disponible = mayor;
  88. 		}else	{
  89. 			printf("Memory out!!\n");
  90. 			exit(0);
  91. 		}
  92. 	}
  93. 	/*
  94. 		Inicializamos los nodos en caso de que no existan
  95. 	*/
  96. 	if(grafo_actual->nodos[origen-1] == NULL)	{
  97. 		grafo_actual->nodos[origen-1] = calloc(1,sizeof(struct nodo));
  98. 		grafo_actual->nodos[origen-1]->id = origen;
  99. 		grafo_actual->total++;
  100. 	}
  101. 	if(grafo_actual->nodos[destino-1] == NULL)	{
  102. 		grafo_actual->nodos[destino-1] = calloc(1,sizeof(struct nodo));
  103. 		grafo_actual->nodos[destino-1]->id = destino;
  104. 		grafo_actual->total++;
  105. 	}
  106.  
  107. 	/*
  108. 		Agregamos las Pesos y Aristas
  109. 	*/
  110. 	add_nodo(grafo_actual,origen,peso,destino);
  111. 	add_nodo(grafo_actual,destino,peso,origen);
  112.  
  113. 	/*
  114. 		Retornamos el grafo_actual
  115. 	*/
  116. 	return grafo_actual;
  117. }
  118.  
  119. void add_nodo(struct grafo *grafo_actual,int origen,int peso,int destino)	{
  120. 	struct nodo *aux = grafo_actual->nodos[origen-1];
  121. 	aux->aristas = realloc(aux->aristas,sizeof(int)*(aux->total+1));
  122. 	aux->vertices = realloc(aux->vertices,sizeof(int)*(aux->total+1));
  123. 	aux->aristas[aux->total]  = peso;
  124. 	aux->vertices[aux->total] = grafo_actual->nodos[destino-1];
  125. 	printf("Uniendo nodos: (%i)--[%i]--(%i)\n",origen,peso,destino);
  126. 	aux->total++;
  127. }
  128.  
  129. int dijkstra(struct nodo *nodo_a,struct nodo *nodo_b)	{
  130. 	struct nodo *inicio =NULL,*pivote = NULL;
  131. 	struct nodo **pendientes = NULL;	//Arreglo de nodos no visitados a un.
  132. 	int i,j,total = 0;
  133. 	int visitado = rand();		//Variable aleatoria para determinar si un Nodo ya fue visitado por esta ocacion
  134. 	int peso_nuevo; 			//Variable temporal para evaluar cual es el menor peso al momento de visitar un nodo
  135. 	i = 0;
  136. 	pendientes = realloc(pendientes,sizeof(struct nodo*)*(total+1));
  137. 	pendientes[total] = nodo_a;	//Nodo inicial a visitar el el nodo A que se recibio como parametr
  138. 	nodo_a->peso_actual = 0;
  139. 	total++;
  140. 	printf("Buscando ruta de %i a %i\n",nodo_a->id,nodo_b->id);
  141. 	while(i < total)	{
  142. 		pivote = pendientes[i];
  143. 		printf("Procesando el nodo %i\n",pivote->id);
  144. 		if(pivote->out != visitado){	//Si aun no Agotamos el nodo actual
  145. 			printf("Visitando %i\n",pivote->id);
  146. 			j = 0;
  147. 			while(j < pivote->total )	{
  148. 				if(pivote->vertices[j]->out != visitado)	{
  149. 					if(pivote->vertices[j]->visitado != visitado)	{
  150. 						printf("El subnodo %i no a sido visitado\n",pivote->vertices[j]->id);
  151. 						pendientes = realloc(pendientes,sizeof(struct nodo*)*(total+1));
  152. 						pendientes[total] = pivote->vertices[j];
  153. 						total++;
  154. 						pivote->vertices[j]->peso_actual = pivote->peso_actual + pivote->aristas[j];
  155. 						pivote->vertices[j]->mejor_ruta = pivote;
  156. 						//printf("Ruta de %i a %i vale %i\n",nodo_a->id,pivote->vertices[j]->id,pivote->vertices[j]->peso_actual);
  157. 					}
  158. 					else	{	//Aqui ya lo visitamos, solo validaremos si la ruta pesa menos por este camino que por que se visito previamente
  159. 						printf("El subnodo %i ya a sido visitado\n",pivote->vertices[j]->id);
  160. 						//printf("El subnodo %i ya a sido visitado\n",pivote->vertices[j]->id);
  161. 						peso_nuevo =  pivote->peso_actual + pivote->aristas[j];
  162. 						printf("%i > %i ? %s\n",pivote->vertices[j]->peso_actual,peso_nuevo,(pivote->vertices[j]->peso_actual > peso_nuevo) ? "si":"no");
  163. 						if(pivote->vertices[j]->peso_actual > peso_nuevo)	{	// Si esta condicion se cumple es mas rapido llegar al nodo pivote->vertices[j] mediante el nodo pivote
  164. 							printf("Nueva mejor ruta a %i con peso de %i\n",pivote->vertices[j]->id,peso_nuevo);
  165. 							pivote->vertices[j]->peso_actual = peso_nuevo;
  166. 							pivote->vertices[j]->mejor_ruta = pivote;
  167. 						}
  168. 						printf("Ruta de %i a %i vale %i\n",nodo_a->id,pivote->vertices[j]->id,pivote->vertices[j]->peso_actual);
  169. 						//En caso de que el if no se cumpla es mas rapido llegar al nodo pivote->vertices[j] de la manera en la ya habia sido visitado previamente
  170. 					}
  171. 				}
  172. 				else	{
  173. 					//printf("El subnodo %i ya a sido visitado\n",pivote->vertices[j]->id);
  174. 					printf("El subnodo %i ya a sido visitado\n",pivote->vertices[j]->id);
  175. 					peso_nuevo =  pivote->peso_actual + pivote->aristas[j];
  176. 					printf("%i > %i ? %s\n",pivote->vertices[j]->peso_actual,peso_nuevo,(pivote->vertices[j]->peso_actual > peso_nuevo) ? "si":"no");
  177. 					if(pivote->vertices[j]->peso_actual > peso_nuevo)	{	// Si esta condicion se cumple es mas rapido llegar al nodo pivote->vertices[j] mediante el nodo pivote
  178. 						printf("Nueva mejor ruta a %i con peso de %i\n",pivote->vertices[j]->id,peso_nuevo);
  179. 						pivote->vertices[j]->peso_actual
  180. 						= peso_nuevo;
  181. 						pivote->vertices[j]->mejor_ruta = pivote;
  182. 					}
  183. 					printf("Ruta de %i a %i vale %i\n",nodo_a->id,pivote->vertices[j]->id,pivote->vertices[j]->peso_actual);
  184. 					//En caso de que el if no se cumpla es mas rapido llegar al nodo pivote->vertices[j] de la manera en la ya habia sido visitado previamente
  185. 				}
  186. 				pivote->vertices[j]->visitado = visitado;
  187. 				j++;
  188. 			}
  189. 			pivote->out = visitado;
  190. 			printf("Nodo %i fuera!\n",pivote->id);
  191. 		}
  192. 		else	{
  193. 			printf("El nodo %i ya esta fuera\n",pivote->id);
  194. 		}
  195. 		i++;
  196. 	}
  197. 	free(pendientes);
  198. 	return nodo_b->peso_actual;
  199. }
  200.  

Título: Re: [Grafo] Base para el Algoritmo de Dijkstra
Publicado por: class_OpenGL en 8 Agosto 2016, 05:01 am
Esto me vendrá bien para aprender el tema de los grafos. ¡Gracias!


Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines