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/* 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
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 /* 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 /* 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" );
}
Mostrar Mensajes
