Algoritmo de Dijkstra paso a paso

[Yoel Alejandro]

Recientemente vi una pregunta de un usuario del foro sobre grafos no dirigidos y distancia mínima entre nodos del mismo. Me puse a invetigar el tema, el cual me pareció realmente interesante y decidí escribir un post al respecto.

El algoritmo de Dijkstra permite encontrar la distancia mínima entre un vértice dado de un grafo no dirigido, y cualquiera otro de sus vértices. No funciona sin embargo si la ponderación entre dos elementos es negativa, es sólo para grafos donde el coste de unir dos nodos cualesquiera es siempre mayor o igual que cero.

http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra
http://es.wikipedia.org/wiki/Anexo:Ejemplo_de_Algoritmo_de_Dijkstra

Un video de youtube que nos explica este tema de una manera excelente es:

[youtube=640,360] https://www.youtube.com/watch?v=yrNAtAIUhJA [/youtube]

A modo de ejemplo, consideremos el grafo (me disculpan la presentación simplemente me puse a escribir sobre una hoja de papel y le tomé fotografías)

En esta imagen, los valores sobre las aristas representan los pesos o costes de transitar los caminos que unen un nodo con el otro. El algoritmo comienza eligiendo un nodo inicial, en este caso digamos que el nodo 0.

Etiquetado de los nodos

Junto con cada nodo asociaremos una etiqueta o label que se compone de un par de valores:

( peso_acumulado, antecesor )

esto es, como primer elemento el peso total acumulado del nodo actual (la suma de los pesos de las aristas recorridas para llegar desde el nodo inicial hasta el nodo actual), y como segundo elemento denotamos el nodo previo al nodo actual. Esto último es importante para reconstruir la ruta seguida para llegar al nodo.

El nodo inicial tiene un peso de 0 (la distancia que lo separa de sí mismo es lógicamente cero), y no tiene antecesor, por lo que se asigna el par compuesto de un "cero" seguido de una "rayita": (0, -)

Vale decir que los restantes nodos comienzan con un peso o coste "infinito", pues aún no hemos calculado su coste.

Cálculo del coste hasta los nodos sucesivos

El siguiente paso es observar todos los nodos que están directamente conectados con este nodo inicial. En nuestro caso, los nodos 1, 2 y 3. El coste de cada nodo será el coste acumulado de su nodo antecesor, sumado al coste del camino que une al antecesor con el nodo actual:

Código [Seleccionar] Expandir


coste de nodo 1: (coste acumulado nodo 0) + (coste camino que une nodos 0 y 1) = 0 + 16 = 16
coste de nodo 2: (coste acumulado nodo 0) + (coste camino que une nodos 0 y 2) = 0 + 10 = 10
coste de nodo 3: (coste acumulado nodo 0) + (coste camino que une nodos 0 y 3) = 0 + 5 = 5

por lo tanto etiquetamos estos nodos sucesores del nodo 0 de la siguiente manera:

Código [Seleccionar] Expandir


nodo 1 ---> ( 16, 0 )     [ pues, su coste acumulado es 16, y procede del nodo 0 ]
nodo 2 ---> ( 10, 0 )     [ ídem ]
nodo 2 ---> ( 5, 0 )     [ ídem ]

Seguidamente, "tachamos" o "marcamos" el nodo 0 como definitivo, y con ellos hemos terminado el primer ciclio de la ejecución de nuestro algoritmo. Queda resaltar que un nodo "tachado" es un nodo que no se vuelve a revisar. El algoritmo terminará cuando todos los nodos estén "tachados".
Hasta ahora vamos así:

Continuación del algoritmo

El algoritmo continúa inspeccionando entre todos los nodos que no han sido tachados o marcados como definiitivos, pero tienen un peso total ya calculado menor a infinito. Esto es, los nodos 1, 2 y 3. De ellos, seleccionamos el de menor coste, que sería el nodo 3 y repetimos el proceso considerándolo como nodo inicial.

Al nodo 3 le suceden, exceptuando el propio nodo 0 que ya fue tachado (repito, los nodos tachados no se vuelven a revisar), los nodos 2 y 4. Sus costes totales se calcularían como:

Código [Seleccionar] Expandir


coste de nodo 2: (coste acumulado nodo 3) + (coste camino que une nodos 3 y 2) = 5 + 4 = 9
coste de nodo 4: (coste acumulado nodo 3) + (coste camino que une nodos 3 y 4) = 5 + 15 = 20

por lo tanto etiquetamos estos nodos sucesores del nodo 3 de la siguiente manera:

Código [Seleccionar] Expandir


nodo 2 ---> ( 9,  3 )     [ costo 9, procediendo del nodo 3 ]
nodo 4 ---> ( 20, 3 )     [ costo 20, procediendo del nodo 3 ]

Mejoramiento del coste

Obsérvese en la última etapa que hasta ahora llevamos del algoritmo, que el coste del nodo 2 mejoró de un valor 10 a un valor 9, al cambiar su antecesor y por lo tanto la ruta seguida.

Para ser más claros, el coste del nodo 2 al tomar la ruta que procede directamente desde el nodo 0 fue de 10. Pero al considerar la ruta que alcanza el nodo 2 desde el nodo 3, o sea la ruta 0-3-2, el coste total acumulado fue 5+4=9. Cuando esto ocurre tachamos la anterior etiqueta del nodo 2 que era (10,0), y la cambiamos por la etiqueta (9,3). Y esto lo debemos hacer cada vez que alcancemos un nodo que habíamos computado, pero esta vez desde una nueva ruta y con un costo menor.

El grafo nos va quedando así, y nótese como se mejora el coste del nodo 2. También nótese que tachamos el nodo 3, es decir lo marcamos como definitivo por eso no lo volveremos a revisar.

Siguiente paso

Revisamos ahora todos los nodos que tienen un coste calculado menor a infinito, en este caso los nodos 1,2  y 4. El de menor coste es el nodo 2, por lo tanto es el nodo que vamos a tomar como inicial.

Los sucesores del nodo 2 son los nodos 1, 4 y 5. Calculamos sus costes:

Código [Seleccionar] Expandir


nodo 1, a partir de 2: 9 + 2 = 11   (mejora el coste)
nodo 5, a partir de 2: 9 + 12 = 21
nodo 4, a partir de 2: 9 + 10 = 19 (mejora el coste)

Marcamos el nodo 2 como definitivo, y continuamos.

Siguiente paso

De los nodos no definitivos que quedan (1, 4 y 5) el de menor coste es el 1. Inspeccionamos sus sucesores, los nodos 5 y 6, al calcular los costes de estos resulta:

Código [Seleccionar] Expandir


nodo 5, a partir de 1: 11 + 4 = 15   (mejora el coste)
nodo 6, a partir de 1: 11 + 6 = 17

Tachamos el nodo 1 y continuamos.

b] Siguiente paso [/b]

De los nodos no definitivos que quedan (4, 5 y 6) el de menor coste es el 5. Inspeccionamos sus sucesores, los nodos 6, 7 y 4, al calcular los costes de estos resulta:

Código [Seleccionar] Expandir


nodo 6, a partir de 5: 15 + 8 = 23   (empeora el coste)
nodo 7, a partir de 5: 15 + 16 = 31
nodo 7, a partir de 5: 15 + 3 = 18

Nótese que al recalcular el nodo 6 desde el nodo 5 se obtiene más bien un costo peor, por lo cual se mantiene su costo anterior que era 17, desde el nodo 1.

Tachamos el nodo 5 y continuamos, nos debe quedar así:

Pasos finales

El algoritmo se continúa repitiendo los pasos anteriores, hasta que no queden nodos sin tachar, es decir, hasta que todos queden como definitivos.

Reconstrucción de la ruta más económica

Una vez terminado, podemos calcular la ruta del coste mínimo desde el nodo inicial 0, hasta cualquiera otro de nuestros nodos. Por ejemplo, desde el nodo 0 hasta el nodo 7, vemos que el coste total es 23 y la ruta se forma regresivamente de la siguiente manera

Código [Seleccionar] Expandir


el nodo 7, procede del nodo 4
el nodo 4, procede del nodo 5
el nodo 5, procede del nodo 1
el nodo 1, procede del nodo 2

etcétera, hasta llegar al nodo inicial. La ruta por lo tanto sería:

0 - 3 - 2 - 1 - 5 - 4 - 7

===================================================================
   PROGRAMA EN C++ PARA EL CALCULO DE LA RUTA MINIMA

Este es un pequeño programa que hice en C++ para computar el grafo anteriormente explicado usando el algoritmo de Dijkstra. Al cambiar la matriz de adyacencia por otra, se puede modificar el programa para trabajar con un grafo diferente. Claro, está un poco rudimentario, lo ideal sería poder pedir al usuario la matriz de adyacencia del grafo de forma interactica a través del teclado, pero hasta ahí no llegué por hoy jeje.

Codifiqué algunos "cout" para que el programa fuese imprimiendo los resultados de las distintas etapas del análisis, de modo que sea más explicativo o pedagógico. Por supuesto, el programa está dado a mejorar ya que esta es una versión muy básica pero es completamente funcional, sólo compilar y probar.

Para nuestro caso la salida final es (luego de imprimir información etapas previas del análisis, jeje)

Código [Seleccionar] Expandir


================================================================

Ruta mas economica entre nodo 0 y nodo 7:

0 - 3 - 2 - 1 - 5 - 4 - 7

Costo total: 23

Por otra parte, creo que el programa no está mal, no es demasiado extenso porque la parte que calcula el Dijkstra sólo llevó 113 líneas de código, el resto del código es inicializando la matriz, declarando los structs, etc.

Código (cpp) [Seleccionar] Expandir


#include <iostream>
#include <iomanip>
#include <list>

/* Definiendo la estructura etiqueta de nodo. Sus campos incluyen
* el número de nodo, el coste total del nodo, y su precedente. */
struct label {
   int nro; /* numero del nodo */
   int prev; /* nodo precedente (-1 para el nodo inicial )*/
   int peso; /* peso o coste total de la trayectoria que
* conduce al nodo, i.e., el coste total desde
* el nodo inicial hasta el actual. Un valor
* de -1 denota el infinito */
   int marca; /* si el nodo ha sido marcado o no */
};
typedef struct label label_t;

using namespace std;

void dijkstra( int, int **, int, int );

int main () {

   /* cantidad total de nodos */
   int numNodos = 8;

   /* Definiendo la matriz de adyacencia */
   int i, j, **A;

   if ( ( A = new int*[numNodos] ) == NULL ) return 1;
   for ( i = 0; i < numNodos; i++ )
      if ( ( A[i] = new int[numNodos] ) == NULL ) return 1;

   for ( i = 0; i < 8; i++ )
      for ( j = 0; j < 8; j++ )
         A[i][j] = 0;

   /* por simplicidad, completamos solo los pares de nodos conectados */
   A[0][1] = 16;
   A[0][2] = 10;
   A[0][3] = 5;

   A[1][0] = 16;
   A[1][2] = 2;
   A[1][5] = 4;
   A[1][6] = 6;

   A[2][0] = 10;
   A[2][1] = 2;
   A[2][3] = 4;
   A[2][4] = 10;
   A[2][5] = 12;

   A[3][0] = 5;
   A[3][2] = 4;
   A[3][4] = 15;

   A[4][2] = 10;
   A[4][3] = 15;
   A[4][5] = 3;
   A[4][7] = 5;

   A[5][1] = 4;
   A[5][2] = 12;
   A[5][4] = 3;
   A[5][6] = 8;
   A[5][7] = 16;

   A[6][1] = 6;
   A[6][5] = 8;
   A[6][7] = 7;

   A[7][4] = 5;
   A[7][5] = 16;
   A[7][6] = 7;

   /* Imprimir la matriz de adyacencia */
   cout << "Matriz de adyacencia:" << endl << endl;
   for ( i = 0; i < 8; i++ ) {
      for ( j = 0; j < 8; j++ )
         cout << setw(2) << A[i][j] << "  ";
      cout << endl;
   }
   cout << endl;

   /* calcular dijkstra a partir del nodo 0, a partir del nofo 7 */
   dijkstra( numNodos, A, 0, 7 );

   /* liberar memoria */
   delete [] A;
   for ( i = 0; i < numNodos; i++ )
      delete A[i];

   return 0;
}

/* Calcula el coste minimo de alcanzar un nodo final 'b'
* grafo no dirigido con N nodos, a partir del nodo inicial 'a',
* dada su matriz de adyacencia A */
void dijkstra( int N, int **A, int a, int b ) {

   label_t *Labels;
   int i, i0, j, peso;
   int *ruta; /* array de nodos de la ruta minima */

   /* Crea din'amicamente el arreglo de etiquetas de nodo */
   if ( ( Labels = new label_t[N] ) == NULL ) return;

   /* nodo inicial 'a' entre 0 y N - 1 */
   if ( a < 0 || a > N - 1 ) return;
   /* nodo final 'a' entre 0 y N - 1 */
   if ( b < 0 || b > N - 1 ) return;

   /* inicializar las etiquetas de nodo */
   for ( i = 0; i < N; i++ ) {
      Labels[i].nro = i;
      if ( i != a ) {
         Labels[i].prev = -1; /* a'un no se ha definido predecesor */
         Labels[i].peso = -1; /* infinito */
         Labels[i].marca = 0;
      }
      else {
         Labels[i].prev = -1; /* a'un no se ha definido predecesor */
         Labels[i].peso = 0; /* coste del nodo inicial a s'i mismo es cero */
         Labels[i].marca = 0;
      }
   }

   /* continuamos este ciclo mientras existan nodos no marcados */
   while ( 1 ) {
      /* busca entre todos los nodos no marcados el de menor peso, descartando los
       * de peso infinito (-1) */
      peso = -1;
      i0 = -1;
      for ( i = 0; i < N; i++ ) {
         if ( Labels[i].marca == 0 && Labels[i].peso >= 0 )
            if ( peso == -1 ) {
               peso = Labels[i].peso;
               i0 = i;
            }
            else if ( Labels[i].peso <= peso ) {
               peso = Labels[i].peso;
               i0 = i;
            }
      }
      if ( i0 == -1 ) { /* termina si no encuentra */
         cout << "Ya no quedan nodos por analizar." << endl;
         break;
      }

      cout << "*** Analizando nodo " << i0 << " ***" << endl;

      /* actualiza el peso de todos los sucesores (si los hay) del nodo
       * encontrado y luego se~nala dicho nodo como marcado */
      for ( i = 0; i < N; i++ ) {
         if ( A[i0][i] > 0 ) {
            /* si el coste acumulado sumado al coste del enlace del nodo i0 al nodo i
             * es menor al coste del nodo i (o si el coste del nodo i es infinito),
             * debemos actualizar */
            if ( Labels[i].peso == -1 || Labels[i0].peso + A[i0][i] < Labels[i].peso ) {
               if ( Labels[i0].peso + A[i0][i] < Labels[i].peso )
                  cout << "   [ mejorando coste de nodo " << i << " ]" << endl;
               Labels[i].peso = Labels[i0].peso + A[i0][i];
               Labels[i].prev = i0;
               cout << "   coste de nodo " << i << " desde nodo " << i0 << ": " << Labels[i].peso << endl;
            }
         }
      }
      Labels[i0].marca = 1;
      cout << "   [ nodo " << i0 << " marcado ]" << endl;

      /* para verificar, imprime los costes calculados hasta el momento */
      for ( i = 0; i < N; i++ ) {
         cout << i << ": [";
         if ( Labels[i].peso == -1 ) cout << "Inf";
         else cout << Labels[i].peso;
         cout << ", " << Labels[i].prev ;
         if ( Labels[i].marca == 1 ) cout <<  ", x]" << endl;
         else cout << "]" << endl;
      }
      cout << endl;

      /* pausa (opcional) */
      cout << "presione ENTER para continuar ...";
      cin.get();
   }

   /* Ruta desde el nodo 'a' hasta el nodo 'b' */
   int longitud = 2;
   i = b;
   while ( ( i = Labels[i].prev ) != a ) longitud++; /* primero estimamos la longitud de la ruta */
   if ( ( ruta = new int[longitud] ) == NULL ) return;

   ruta[longitud - 1] = b; /* luego rellenamos */
   i = b;
   j = 0;
   for ( j = 1; j < longitud; j++ ) {
      i = Labels[i].prev;
      ruta[longitud - j - 1] = i;
   }

   cout << "================================================================" << endl;
   cout << endl << "Ruta mas economica entre nodo " << a << " y nodo " << b << ":" << endl << endl;
   for ( i = 0; i < longitud; i++ ) {
      cout << ruta[i];
      if ( i < longitud - 1 ) cout << " - ";
   }
   cout << endl << endl << "Costo total: " << Labels[b].peso << endl << endl;

   delete ruta;
   delete [] Labels;
}

[vk496]

Muy bueno... Y muy útil este algoritmo, tiene muchas aplicaciones en la vida real (no sabía hasta que punto si no lo hubiese descubierto)

Salu2

[marrison]

Muchas gracias amigo por la explicacion, de verdad que me ha ayudado mucho, aunque yo lo tengo que hacer para c..

[Yoel Alejandro]

Bueno marrison, si es para C la verdad es que no tienes mucho que cambiar. Tuve cuidado al elaborar el código de modo que fuera en su mayor parte compatible con C.

Lo único que tendrías que adaptar en la gestión dinámica de memoria para los arreglos que se crean en tiempo de ejecución. O sea, el uso de malloc(), realloc() y free(), en lugar de la combinación new y delete de C++.

De todos modos voy a ver si en estos días tengo un tiempo y versiono el código completamente a C.

Y un detalle, en el algoritmo que propuse falta implementar una "cola de prioridad", que puede optimizar la ejecución. En esta cola se van guardando los nodos en función de su peso, colocando de primero los de menor coste. De esta manera no hay que calcular el mínimo con cada ciclo, puesto que dicho nodo más económico siempre de está de primero en la cola y sólo hay que cogerlo de allí.

Un saludo ...

[marrison]

La verdad es que me harias un gran favor, gracias a tu aporte entiendo el algoritmo, pero no tengo ni idea de como implementarlo... 

[Yoel Alejandro]

Voy a trabajar pronto en una versión completamente en C, que implemente cola de prioridad

[sabeeee]

Jajaja que genialidad. 

[daryo]

chincheta!

[Yoel Alejandro]

Ahora sí que sí, ya lo pude terminar jajaja 

El inicio de estre post me referí a un programa que emplea el algoritmo de Dijkstra para calcular la ruta más económica entre dos puntos de un grafo no dirigido. La versión inicialmente publicada fue en C++. Ahora voy con una vesión completamente en C, que además implementa una cola de prioridad para seleccionar más eficientemente el nodo objetivo a analizar en cada ciclo del algoritmo.

El principio es sencillo. Inicialmente la cola contiene únicamente al nodo inicial del grafo. Seguidamente se analizan todos los sucesores (no marcados) del nodo objetivo, y se evalúa o re-evalua su coste, y se coloca ordenadamente como corresponda en la cola de prioridad. La cola siempre permanece ordenada según el coste del nodo, de menor a mayor, puesto que cuando se inserta un nuevo elemento se lo hace en el lugar que corresponde según su valor.

En el caso que un nodo al ser re-evaluado disminuye o mejora su coste, entonces debe ser reubicado en la cola. Para ello, lo que hacemos es retirarlo de la cola y luego reinsertarlo en la posición adecuada.

Luego de ésto, el nodo objetivo es "marcado" y por lo tanto sacado de la cola puesto que no volverá a ser analizado en ejecuciones posteriores del algoritmo.

La versión a C se logró simplemente cambiando algunos "cout" a "printf()", y reemplazando el típico new/delete de C++ por el malloc()/free() de C. Lo que fue un poquito más complicado fue tener que implementar "manualmente" una cola de prioridad en C, porque no podemos usar la clase stack de la STL de C++.

A continuación el programa como quedó, y advierto que ahora si creció un poco superando las 300 líneas por eso lo voy a dividir por partes. Recomiendo leer con atención la función insert() que se ocupa de agregar un elemento a la cola según el coste del número de nodo indicado.

Espero con esto haber disipado las dudas de algunos de los lectores de mi tema, y cualquier sugerencia o recomendación no duden en escribir

Bibliotecas y prototipos

Código (cpp) [Seleccionar] Expandir


/* Programa que utiliza el algoritmo de Dijsktra para encontrar el
* camino más corto o económico entre dos puntos de un grafo
* no dirigido.
*/

#include <stdlib.h>
#include <stdio.h>

/* Definiendo la estructura etiqueta de nodo. Sus campos incluyen
* el n'umero de nodo, el coste total del nodo, y su precedente. */
struct label {
int nro; /* numero del nodo */
int prev; /* nodo precedente (-1 para el nodo inicial )*/
int peso; /* peso o coste total de la trayectoria que
* conduce al nodo, i.e., el coste total desde
* el nodo inicial hasta el actual. Un valor
* de -1 denota el infinito */
int marca; /* si el nodo ha sido marcado o no */
};
typedef struct label label_t;

/* Cola de Prioridad de n'umeros de nodo */
struct node {
int data;
struct node * nextPtr; /* apuntador al siguiente nodo de la cola */
};
typedef struct node node_t;

int isEmpty( node_t * ); /* decide si cola es vac'ia */
int insert( node_t **, int, label_t * ); /* agrega un nodo ordenadamente a la cola */
void quit( node_t **, int ); /* retira un nodo espec'ifico de la cola */
int pop( node_t ** ); /* retira el primer nodo de la cola */
void printQueue( node_t * ); /* imprimir los valores almacenados en la cola */

/* Funci'on que calcula la distancia m'inima de cualquiera de los
* nodos al primero */
void dijkstra( int, int **, int, int );

Función MAIN , simplemente crea la matriz de adyacencia y llama al Dijkstra

Código (cpp) [Seleccionar] Expandir


int main () {

int i, j;

/* cantidad total de nodos */
int numNodos = 8;

/* Definiendo la matriz de adyacencia */
int **A;
if ( ( A = (int **) malloc( numNodos * sizeof(int *) ) ) == NULL ) return 1;
for ( i = 0; i < numNodos; i++ )
if ( ( A[i] = (int *) malloc( numNodos * sizeof(int) ) ) == NULL ) return 1;

for ( i = 0; i < 8; i++ )
for ( j = 0; j < 8; j++ )
A[i][j] = 0;

/* por simplicidad, completamos solo los pares de nodos conectados */
A[0][1] = 16;
A[0][2] = 10;
A[0][3] = 5;

A[1][0] = 16;
A[1][2] = 2;
A[1][5] = 4;
A[1][6] = 6;

A[2][0] = 10;
A[2][1] = 2;
A[2][3] = 4;
A[2][4] = 10;
A[2][5] = 12;

A[3][0] = 5;
A[3][2] = 4;
A[3][4] = 15;

A[4][2] = 10;
A[4][3] = 15;
A[4][5] = 3;
A[4][7] = 5;

A[5][1] = 4;
A[5][2] = 12;
A[5][4] = 3;
A[5][6] = 8;
A[5][7] = 16;

A[6][1] = 6;
A[6][5] = 8;
A[6][7] = 7;

A[7][4] = 5;
A[7][5] = 16;
A[7][6] = 7;

/* Imprimir la matriz de adyacencia */
printf( "Matriz de adyacencia:\n\n" );
for ( i = 0; i < 8; i++ ) {
for ( j = 0; j < 8; j++ )
printf( "%2d  ", A[i][j] );
printf( "\n" );
}
printf( "\n" );

/* calcular dijkstra a partir del nodo 0, a partir del nofo 7 */
dijkstra( numNodos, A, 0, 7 );

/* liberar memoria */
for ( i = 0; i < numNodos; i++ )
free( A[i] );
free( A );

return 0;
}

Algoritmo de Dijsktra

Código (cpp) [Seleccionar] Expandir


/* Calcula el coste m'inimo de alcanzar un nodo final 'b'
* grafo no dirigido con N nodos, a partir del nodo inicial 'a',
* dada su matriz de adyacencia A */
void dijkstra( int N, int **A, int a, int b ) {

label_t *Labels;
int i, i0, j, peso;
int *ruta; /* array de nodos de la ruta minima */

node_t *Cola = NULL; /* cola de prioridad */

/* Crea din'amicamente el arreglo de etiquetas de nodo */
if ( ( Labels = malloc( N * sizeof( label_t ) ) ) == NULL ) return;

/* nodo inicial 'a' entre 0 y N - 1 */
if ( a < 0 || a > N - 1 ) return;
/* nodo final 'a' entre 0 y N - 1 */
if ( b < 0 || b > N - 1 ) return;

/* inicializar las etiquetas de nodo */
for ( i = 0; i < N; i++ ) {
Labels[i].nro = i;
if ( i != a ) {
Labels[i].prev = -1; /* a'un no se ha definido predecesor */
Labels[i].peso = -1; /* infinito */
Labels[i].marca = 0;
}
else {
Labels[i].prev = -1; /* a'un no se ha definido predecesor */
Labels[i].peso = 0; /* coste del nodo inicial a s'i mismo es cero */
Labels[i].marca = 0;
}
}

/* agregamos el nodo inicial como primer elemento de la cola */
insert( &Cola, a, Labels );

/* continuamos este ciclo mientras existan nodos en la cola */
while ( !isEmpty( Cola ) ) {

/* toma como objetivo el primer elemento de la cola de prioridad */
i0 = pop( &Cola );

printf( "*** Analizando nodo %d ***\n", i0 );

/* actualiza el peso de todos los sucesores no marcados (si los hay) del nodo
* encontrado y luego se~nala dicho nodo como marcado */
for ( i = 0; i < N; i++ ) {
if ( A[i0][i] > 0 && Labels[i].marca == 0 ) {
/* si el coste es infinito, actualizar y añadir a la cola */
if ( Labels[i].peso == -1 ) {
Labels[i].peso = Labels[i0].peso + A[i0][i];
insert( &Cola, i, Labels );
}
/* si el coste acumulado sumado al coste del enlace del nodo i0 al nodo i
* es menor al coste del nodo i, actualizar al valor del costo menor y
* reubicar en la cola */
else if ( Labels[i0].peso + A[i0][i] < Labels[i].peso ) {
printf( "   * advertencia: mejorando coste de nodo %d\n", i );
Labels[i].peso = Labels[i0].peso + A[i0][i];
quit( &Cola, i ); /* para reubicar, quitamos y luego a~nadimos el nodo */
insert( &Cola, i, Labels );
}
Labels[i].prev = i0;
printf( "   coste de nodo %d desde nodo %d: %d\n", i, i0, Labels[i].peso );
}
}
Labels[i0].marca = 1;
printf( "   * nodo %d marcado\n", i0 );

/* para verificar, imprime los costes calculados hasta el momento */
for ( i = 0; i < N; i++ ) {
printf( "%d: [", i);
if ( Labels[i].peso == -1 ) printf( "Inf" ); else printf( "%d", Labels[i].peso);
printf( ", %d", Labels[i].prev );
if ( Labels[i].marca == 1 ) printf( ", x]\n" ); else printf( "]\n" );
}

/* imprimir cola prioridad de nodos */
printf( "cola de nodos en orden de prioridad es:\n" );
printQueue( Cola );

/* pausa (opcional) */
printf( "\npresione ENTER para continuar ..." );
getchar();
}
printf( "Ya no quedan nodos por analizar.\n" ); /* mensaje final */

/* Ruta desde el nodo 'a' hasta el nodo 'b' */
int longitud = 2;
i = b;
while ( ( i = Labels[i].prev ) != a ) longitud++; /* primero estimamos la longitud de la ruta */
if ( ( ruta = malloc( longitud * sizeof(int) ) ) == NULL ) return;

ruta[longitud - 1] = b; /* luego rellenamos */
i = b;
j = 0;
for ( j = 1; j < longitud; j++ ) {
i = Labels[i].prev;
ruta[longitud - j - 1] = i;
}

printf( "================================================================\n" );
printf( "\nRuta mas economica entre nodo %d y nodo %d:\n\n", a, b );
for ( i = 0; i < longitud; i++ ) {
printf( "%d", ruta[i]);
if ( i < longitud - 1 ) printf( " - " );
}
printf( "\n\nCosto total: %d\n\n", Labels[b].peso );

free( ruta );
free( Labels );
}

Métodos asociados a la cola de prioridad

Código (cpp) [Seleccionar] Expandir


/* Devuelve 1 si la cola está vacía, 0 si no lo está. */
int isEmpty( node_t * head ) {

return head == NULL;
}

/* Insertar ordenadamente en la cola.
* Devuelve 0 si terminó con éxito, y 1 si ocurrió un error
* de asignación de memoria. */
int insert( node_t ** frontPtr, int nodeNumber, label_t * Labels ) {

node_t *newPtr, *currentPtr, *prevPtr;

if ( ( newPtr = malloc( sizeof( node_t ) ) ) == NULL ) return 1;

/* busca el último nodo menor al que se quiere insertar */
currentPtr = *frontPtr;
prevPtr = NULL;
while ( currentPtr != NULL && Labels[currentPtr->data].peso < Labels[nodeNumber].peso ) {
prevPtr = currentPtr;
currentPtr = currentPtr->nextPtr;
}

/* inserta el nuevo nodo */
newPtr->data = nodeNumber;
if ( currentPtr != NULL )
newPtr->nextPtr = currentPtr;
else
newPtr->nextPtr = NULL;

if ( prevPtr != NULL )
prevPtr->nextPtr = newPtr;
else
*frontPtr = newPtr;

return 0;
}

/* Remover de la cola el nodo con el valor específico, si lo encuentra */
void quit( node_t ** frontPtr, int data ) {

node_t *prevPtr = NULL, *currPtr = *frontPtr;

/* busca el nodo con el valor espec'ifico */
while ( currPtr != NULL && currPtr->data != data ) {
prevPtr = currPtr;
currPtr = currPtr->nextPtr;
}
if ( currPtr == NULL ) return; /* y termina si no encuentra */

/* si encuentra el nodo, lo remueve */
if ( prevPtr != NULL )
prevPtr->nextPtr = currPtr->nextPtr;
else
*frontPtr = currPtr->nextPtr;

free( currPtr );
}

/* Retirar el primer elemento de la cola.
* Precaución: Devuelve cero si la cola est'a vacía.
*/
int pop( node_t **frontPtr ) {

node_t *auxPtr;
int data;

if ( *frontPtr != NULL ) {
auxPtr = *frontPtr;
*frontPtr = (*frontPtr)->nextPtr;
data = auxPtr->data;
free( auxPtr );
return data;
}
else
return 0;
}

void printQueue( node_t *queue ) {

node_t *currPtr = queue;

if ( currPtr == NULL ) {
printf( "(vacio)\n" );
return;
}

while ( currPtr != NULL ) {
printf( "%d", currPtr->data );
if ( currPtr->nextPtr != NULL ) printf( " -> " );
currPtr = currPtr->nextPtr;
}
printf( "\n" );
}

[MeCraniDOS]

Recientemente vi una pregunta de un usuario del foro sobre grafos no dirigidos y distancia mínima entre nodos del mismo. Me puse a invetigar el tema, el cual me pareció realmente interesante y decidí escribir un post al respecto.

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