Algoritmo de Dijkstra paso a paso

[vk496]

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 

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 

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 

Un saludo

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

Salu2

[Yoel Alejandro]

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.

[marrison]

Muchisimas gracias, de verdad 

[elProfeta1979]

Código (c) [Seleccionar] Expandir

#define INFINITO 1.0E+30
#define NODOS 5
#define MIEMBRO 1
#define NO_MIEMBRO 0
void short_path(int matriz[][NODOS], int s, int t, int *pd, int precede[]){
  int distancia[NODOS];
  int perm[NODOS];
  int corriente, i, k , dc, menor_dist, nueva_dist;

  for(i = 0; i < NODOS; i++){
    perm[i] = NO_MIEMBRO;
    distancia[i] = INFINITO;
  }
  perm[s] = MIEMBRO;
  distancia[s] = 0;
  corriente = s;
  while(corriente != t){

    menor_dist = INFINITO;
    dc = distancia[corriente];

    for(i = 0; i < NODOS; i++){
      nueva_dist = dc + matriz[corriente][i];
      if(nueva_dist < distancia[i]){
        distancia[i] = nueva_dist;
        precede[i] = corriente;
      }
      if(distancia[i] < menor_dist){
        menor_dist = distancia[i];
        k=i;
      }
    }//fin de for
    corriente = k;
    perm[corriente]= MIEMBRO;
  }//fin de while
  *pd = distancia[i];
}


bueno gente aporto este código, si alguien comenta.