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

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 ]

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

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

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)

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

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

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

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

Ruta mas economica entre nodo 0 y nodo 7:

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

Costo total: 23

#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;
}

/* 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 );

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;
}

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

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