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

 

 


Tema destacado: Usando Git para manipular el directorio de trabajo, el índice y commits (segunda parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Auxilio con ALGORITMO DE DIJKSTRA!!!!! :'c
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Auxilio con ALGORITMO DE DIJKSTRA!!!!! :'c  (Leído 2,472 veces)
axel19

Desconectado Desconectado

Mensajes: 4


Ver Perfil
Auxilio con ALGORITMO DE DIJKSTRA!!!!! :'c
« en: 3 Junio 2018, 05:30 am »

DIJKSTRA!!!!
Estoy trabajando en un proyecto el entrega la ruta más corta de un nodo a otro dentro de un grafo
Este grafo lo tengo representado como una matriz de costos

He trabajado en ello y lo tengo "RELATIVAMENTE RESUELTO"

Lo que sucede es que me genera una ruta corta aunado a las aristas consiguientes

Por ejemplo si to quiero ir del nodo A al B...

A-------3-------B
|                    |
2                    5
|                    |
C-------9-------D

La ruta sería A->B pero el programa toma A->C->D->B, esto porque la arista de A->C es menor que la de A->B

Como puedo resolver este problema????

Y si alguien lo tiene, me podría proporcionar un codigo usando el algoritmo de Dijkstra???

Añado mi codigo a mi publicación para que lo puedan observar y me puedan auxiliar en esto

En verdad me urge tener este codigo, de antemano muchas gracias y excelente dia c:


PD: SUELO TENER ALGO DE CODIGO BASURA EN MIS PROYECTOS POR SI ENCUENTRAN ALGO QUE NO SE OCUPE PARA NADA, ES UN MAL HABITO QUE TENGO Y SIGO TRABAJANDO EN ELLO :'c

Código
  1. #include<stdio.h>
  2. #include<conio.h>
  3. #define max 6
  4. #define INFINITO 999999
  5.  
  6. /*
  7. --------------- SABADO 2 DE JUNIO 2018
  8. *************** PROGRAMA: 0206
  9. ***************     AXEL RODRIGUEZ
  10. ***************      METRO1 \ ESTRUCTURA DE DATOS
  11. */
  12. int Menor(int distancia[max],int n, int visita_bandera[max])
  13. { int menor = INFINITO;
  14. int i;
  15. for (i=0;i<max;i++)
  16. {
  17.  
  18. if ( (distancia[i] ) < menor )
  19. {
  20. menor = distancia[i];
  21. }
  22. }
  23. return menor;                
  24. }
  25.  
  26. void Dijkstra (int matriz[max][max], int nodo_inicial, int nodo_final)
  27. {
  28. int i,j;
  29. int auxiliar[max][max];  
  30. int distancia[max]={'\0'}; //VECTOR DONDE ESTARAN LAS DISTANCIAS GUARDADAS
  31. int analisis[max]={'\0'}; //VECTOR DE FILA QUE SE VA A ANALIZAR
  32. int visita[max]={'\0'}; //VECTOR EN EL QUE SE GUARDARAN LOS NODOS YA VISITADOS
  33. int visita_bandera[max]={'\0'};
  34. int z=1;
  35.  
  36. for (i=0 ; i<max ; i++) //DONDE NO EXISTA ADYACENCIA, LO MANDAMOS A UN VALOR MUUUUY ALTO PARA QUE NO SEA UTILIZADA
  37. { //UTILIZAMOS UNA //VECTOR EN EL QUE SE GUARDARAN LOS NODOS YA VISITADOS
  38. for (j=0 ; j<max ; j++)  
  39. {
  40. if (matriz[i][j] == 0)
  41. {
  42. auxiliar[i][j] = 999;
  43. }
  44. else{
  45. auxiliar[i][j] = matriz[i][j];
  46. }
  47. }
  48. }
  49.  
  50.  
  51. distancia[0]=0;
  52. visita[0]=nodo_inicial;
  53. visita_bandera[nodo_inicial]=1;
  54.  
  55. do{
  56. rutina:
  57.  
  58. for(i=0 ; i<max ; i++)                      
  59. {
  60. analisis[i] = auxiliar [nodo_inicial][i]; //GUARDAMOS EN ANALISIS[] LA FILA COMPLETA DONDE ESTE EL NODO INICIAL
  61. }
  62.  
  63. int menor_analisis;
  64.  
  65. menor_analisis = Menor (analisis, 6, visita_bandera); //SE HACE USO DE LA FUNCION MENOR, ENVIANDOLE DE PARAMETROS EL VECTOR A ANALIZAR Y EL NUMERO
  66. //DE ELEMENTOS DEL MISMO
  67.  
  68. int vist,reaccion; // EN VIST SE GUARDARA EL NODO VISITADO Y REACCION ES UNA BANDERA LA CUAL SERVIRA PARA DECIRNOS SI EL NODO YA FUE VISITADO
  69. for(i=0 ; i<max ; i++) // O NO Y DE ESTE MODO EVITAR LOS BUCLES INFINITOS
  70. {                                                    
  71. if (menor_analisis == auxiliar[nodo_inicial][i])
  72. { // ENCUENTRA EL ELEMENTO EN LA MATRIZ DONDE ESTE EL DATO MENOR Y LA GUARDA EN VIST
  73. vist = i;
  74. break;
  75. }
  76. }
  77.  
  78. for(i=0 ; i<max ; i++) // O NO Y DE ESTE MODO EVITAR LOS BUCLES INFINITOS
  79. {                                                    
  80. if (menor_analisis == auxiliar[nodo_inicial][i])
  81. { // ENCUENTRA EL ELEMENTO EN LA MATRIZ DONDE ESTE EL DATO MENOR Y LA GUARDA EN VIST
  82. vist = i;
  83.  
  84. }
  85. }
  86.  
  87. for (i=0 ; i<max ; i++)
  88. {
  89. if (vist == visita[i])
  90. {
  91. reaccion=19;
  92. }
  93. else{
  94. reaccion=0; // SI EL NODO NO HA SIDO VISITADO, REACCION ES 0, Y ESTOS NODOS SE MANDAN A INFINITO PARA QUE NO SE PUEDAN UTILIZAR
  95. auxiliar[nodo_inicial][vist]=INFINITO;
  96. auxiliar[vist][nodo_inicial]=INFINITO;
  97. }
  98. }
  99.  
  100. if(reaccion ==19)
  101. {
  102. auxiliar[vist][nodo_inicial]=INFINITO;
  103. auxiliar[nodo_inicial][vist]=INFINITO;
  104. goto rutina;
  105. }
  106.  
  107. distancia[z]=menor_analisis; // SE GUARDA EN DISTANCIA LA ARISTA DE MENOR TAMAÑO
  108. visita[z]=vist; // SE GUARDA EN VISITA EL NODO YA VISITADO
  109.  
  110. nodo_inicial = visita[z]; // SE IGUALA NODO INICIAL CON EL NODO ULTIMO VISITADO PARA QUE, CUANDO SE HAYA VISITADO
  111. z++; // EL NODO_FINAL, SE DETENGAN LAS ITERACIONES
  112.  
  113. } while (nodo_inicial!=nodo_final);
  114.  
  115. printf(" RUTA A SEGUIR --->  ");
  116. for (j=0 ; j<6 ; j++)
  117. {
  118.  
  119. printf ("%d ", visita[j]+1);
  120. if (visita[j] == nodo_final)
  121. {
  122. break;
  123. }
  124. }
  125. int sumatoria=0;
  126. for (j=0;j<6;j++)
  127. {
  128. sumatoria=sumatoria+distancia[j];
  129. }
  130. printf("DISTANCIA RECORRIDA -->  %d", sumatoria);
  131.  
  132.  
  133. }
  134.  
  135. int main(){
  136. int i,j; // j-> fila    i-> columna
  137. //int matriz[5][5];
  138. int matriz [6][6]= {    0,4,2,0,0,0,
  139. 4,0,1,5,0,0,
  140. 2,1,0,8,9,0,
  141. 0,5,8,0,2,6,
  142. 0,0,9,2,0,2,
  143. 0,0,0,6,2,0}; //ESTA MATRIZ ES EL GRAFO, EN ESENCIA ESTARIA DE ESTE MODO
  144.  
  145. /*
  146. NODO 2 --- 5 ----NODO 4
  147. /   | / | \
  148.      4    | / |   \
  149. /       |   / |        \
  150.      NODO 1    1 8 2  NODO 6
  151.  \     |  / |         /
  152.    2   | / |       /
  153.     \  |/ |      /
  154.      NODO 3 ----9----- NODO 5 */
  155. int auxiliar[6][6];  
  156. int distancia[6]={'\0'}; //VECTOR DONDE ESTARAN LAS DISTANCIAS GUARDADAS
  157. int analisis[6]={'\0'}; //VECTOR DE FILA QUE SE VA A ANALIZAR
  158. int visita[6]={'\0'}; //VECTOR EN EL QUE SE GUARDARAN LOS NODOS YA VISITADOS
  159.  
  160.  
  161. for (i=0; i<6 ; i++)
  162. {
  163. for (j=0; j<6; j++)
  164. {
  165. printf(" %d", matriz[i][j]);
  166. }
  167. printf("\n");
  168. }
  169. printf("\n\n\n");
  170. int nodo_inicial;
  171. int nodo_final;
  172. int z=1;
  173. mm:
  174. printf("Nodo inicial--> ");
  175. scanf("%d",&nodo_inicial);
  176. printf("Nodo final--> ");
  177. scanf("%d",&nodo_final);
  178. printf("\n\n");
  179.  
  180. nodo_inicial=nodo_inicial-1;
  181. nodo_final=nodo_final-1;
  182.  
  183. if (nodo_inicial<nodo_final){
  184. Dijkstra(matriz,nodo_inicial,nodo_final);
  185. printf("\n\n");  }
  186.  
  187. if (nodo_inicial>nodo_final){
  188. Dijkstra(matriz,nodo_final,nodo_inicial);
  189. printf("\n\n");
  190. }
  191. goto mm;
  192.  
  193. return 0;
  194. }
  195.  


En línea

MAFUS


Desconectado Desconectado

Mensajes: 1.603



Ver Perfil
Re: Auxilio con ALGORITMO DE DIJKSTRA!!!!! :'c
« Respuesta #1 en: 3 Junio 2018, 10:23 am »

Tu fallo está en que dado un camino te quedas con el tramo más corto, para todo el camino debes devolver la suma de todos los tramos.


En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Algoritmo de Dijkstra en Visual Basic
Programación Visual Basic
laukibuk 4 13,580 Último mensaje 17 Enero 2008, 07:32 am
por cobein
Algoritmo para un ejercicio; ¿Doble dijkstra?
Programación General
astinx 2 3,692 Último mensaje 16 Febrero 2012, 19:27 pm
por astinx
[Grafo] Base para el Algoritmo de Dijkstra
Programación C/C++
AlbertoBSD 1 3,222 Último mensaje 8 Agosto 2016, 05:01 am
por class_OpenGL
Algoritmo de Dijkstra
Programación C/C++
castrokin 1 3,981 Último mensaje 6 Agosto 2021, 09:15 am
por fzp
Algoritmo Dijkstra
Programación C/C++
castrokin 0 2,034 Último mensaje 6 Marzo 2022, 02:56 am
por castrokin
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines