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