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

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Algoritmo de Dijkstra paso a paso
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 [2] Ir Abajo Respuesta Imprimir
Autor Tema: Algoritmo de Dijkstra paso a paso  (Leído 35,061 veces)
vk496

Desconectado Desconectado

Mensajes: 205


Ver Perfil
Re: Re: Algoritmo de Dijkstra paso a paso
« Respuesta #10 en: 10 Enero 2015, 19:45 pm »

Si te interesan los grafos y calculo de distancias minimas, tambien le puedes echar un vistazo al Algoritmo de Floyd, tienes que ir calculando matrices bidimensionales como vertices tiene el grafo  :laugh:

Con Dijkstra solo calculas la distancia minima desde un vertice inicial al resto, en cambio con Floyd puedes calcular la distancia minima entre cualquier vertice  :rolleyes:

Por poner un ejemplo, si quieres saber la distancia minima de B a C y F, aplicas Dijkstra, pero ahora quieres saber tambien de D a E y F, tienes que volver a aplicar el algoritmo.
En cambio aplicando una unica vez Floyd sacas todas las distancias minimas entre todos los vertices  ;D

Un saludo

Esto si que es útil! Voy a investigar sobre ello... No llegué a darlo en Matemáticas

Salu2


En línea

Yoel Alejandro

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Re: Algoritmo de Dijkstra paso a paso
« Respuesta #11 en: 11 Enero 2015, 01:40 am »

Entiendo el planteamiento al respecto del algoritmo de Floyd, investigaré y posiblemente publique un post al respecto.

Por los momentos estoy terminando algunos detalles que faltaban al programa inicial, pues sabes, un trabajo no está completo hasta que está completo, jejeje

Y sobre todo ayudar a un par de lectores que tenían dudas de este tema en particular, espero que este aporte les disipe al respecto.


En línea

Saludos, Yoel.
P.D..-   Para mayores dudas, puedes enviarme un mensaje personal (M.P.)
marrison

Desconectado Desconectado

Mensajes: 179



Ver Perfil
Re: Algoritmo de Dijkstra paso a paso
« Respuesta #12 en: 11 Enero 2015, 11:26 am »

Muchisimas gracias, de verdad  ;D
En línea

"Es genial trabajar con ordenadores. No discuten, lo recuerdan todo y no se beben tu cerveza" (Paul Leary)

"Controlar la complejidad es la esencia de la programación" (Brian Kernigan)

"Primero resuelve el problema. Entonces, escribe el código" (John Johnson)

"640K deberían ser suficientes para todo el mundo" (Bill Gates, 1981)
elProfeta1979

Desconectado Desconectado

Mensajes: 9


Ver Perfil
Re: Algoritmo de Dijkstra paso a paso
« Respuesta #13 en: 16 Enero 2015, 01:40 am »

Código
  1. #define INFINITO 1.0E+30
  2. #define NODOS 5
  3. #define MIEMBRO 1
  4. #define NO_MIEMBRO 0
  5. void short_path(int matriz[][NODOS], int s, int t, int *pd, int precede[]){
  6.  int distancia[NODOS];
  7.  int perm[NODOS];
  8.  int corriente, i, k , dc, menor_dist, nueva_dist;
  9.  
  10.  for(i = 0; i < NODOS; i++){
  11.    perm[i] = NO_MIEMBRO;
  12.    distancia[i] = INFINITO;
  13.  }
  14.  perm[s] = MIEMBRO;
  15.  distancia[s] = 0;
  16.  corriente = s;
  17.  while(corriente != t){
  18.  
  19.    menor_dist = INFINITO;
  20.    dc = distancia[corriente];
  21.  
  22.    for(i = 0; i < NODOS; i++){
  23.      nueva_dist = dc + matriz[corriente][i];
  24.      if(nueva_dist < distancia[i]){
  25.        distancia[i] = nueva_dist;
  26.        precede[i] = corriente;
  27.      }
  28.      if(distancia[i] < menor_dist){
  29.        menor_dist = distancia[i];
  30.        k=i;
  31.      }
  32.    }//fin de for
  33.    corriente = k;
  34.    perm[corriente]= MIEMBRO;
  35.  }//fin de while
  36.  *pd = distancia[i];
  37. }


bueno gente aporto este código, si alguien comenta.
En línea

Páginas: 1 [2] Ir Arriba Respuesta Imprimir 

Ir a:  

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