El Algortimo de Dijkstra, también denominado Algoritmo de caminos mínimos, es un modelo que se clasifica dentro de los algoritmos de búsqueda. Su objetivo, es determinar la ruta más corta, desde el nodo origen, hasta cualquier nodo de la red. Su metodología se basa en iteraciones, de manera tal que en la práctica, su desarrollo se dificulta a medida que el tamaño de la red aumenta, dejándolo en clara desventaja, frente a métodos de optimización basados en programación matemática.
¿Qué tipos de redes pueden resolverse por medio del Algortimo de Dijkstra?
Este algoritmo, al igual que el método de Floyd, tienen la capacidad de resolver el problema de la ruta más corta, tanto para redes cíclicas, como para redes acíclicas. De manera tal que los bucles que presente una red, no restringen el uso del algoritmo.
El algoritmo de Dijkstra hace uso y define etiquetas a partir del nodo origen y para cada uno de los nodos subsiguientes. Estas etiquetas contienen información relacionada con un valor acumulado del tamaño de los arcos y con la procedencia más próxima de la ruta.
Las etiquetas corresponden a los nodos, no a los arcos. En el algortimo de Dijkstra, estas etiquetas son temporales y permanentes. Las etiquetas temporales son aquellas que son susceptibles de modificarse mientras exista la posibilidad de hallar para sí, una ruta más corta; de lo contrario, dicha etiqueta pasa a ser permanente.
Etiqueta = [acumulado, nodo procedente] iteración
Algoritmo de Dijkstra – Ejemplo
Teniendo en cuenta la siguiente red, que tiene como origen el nodo 1:
Procedemos con las iteraciones, partimos de la iteración 0, es decir, asignar la etiqueta para el nodo origen:
Iteración 0
En este paso, asignamos una etiqueta permanente para el nodo origen. Recordemos que la etiqueta se compone por un valor acumulado, que en este caso debe ser 0, ya que es el punto base y que no existe procedencia:
Etiqueta nodo 1 = [valor acumulado, procedencia] iteración
Etiqueta nodo 1 = [0, -] 0
Iteración 1
En este paso, evaluamos a cuáles nodos se puede llegar desde el nodo 1. En este caso se puede llegar a los nodos 2 y 3. De manera que debemos asignar las etiquetas para cada nodo:
Etiqueta nodo 2 = [valor acumulado, procedencia] iteración
Etiqueta nodo 2 = [0 + 100, 1] 1
0 es el valor acumulado en la etiqueta del nodo de procedencia, en este caso el valor acumulado para el nodo 1. 100 es el valor del arco que une el nodo procedencia (1) y el nodo destino (2). 1 es el número de la iteración.
Etiqueta nodo 3 = [valor acumulado, procedencia] iteración
Etiqueta nodo 3 = [0 + 30, 1] 1
En este caso, podemos observar que la etiqueta del nodo 3, ya contiene el menor valor acumulado posible para llegar a este. Ya que 30 es la mínima distancia posible, toda vez que para llegar al nodo 3 por medio del nodo 2, tendrá que recorrer como mínimo el valor absoluto del arco que une el origen con el nodo 2 = 100. Así entonces, la etiqueta del nodo 3 pasa a ser permanente.
Tabulamos la iteración 1:
Iteración 2:
En este paso, evaluamos las posibles salidas desde el nodo 3, es decir los nodos 4 y 5. De manera que debemos asignar las etiquetas para cada nodo:
Etiqueta nodo 4 = [valor acumulado, procedencia] iteración
Etiqueta nodo 4 = [30 + 10, 3] 2
Etiqueta nodo 4 = [40, 3] 2
30 es el valor acumulado en la etiqueta del nodo de procedencia, en este caso el valor acumulado para el nodo 3. 10 es el valor del arco que une el nodo procedencia (3) y el nodo destino (4). 2 es el número de la iteración.
Etiqueta nodo 5 = [valor acumulado, procedencia] iteración
Etiqueta nodo 5 = [30 + 60, 3] 2
Etiqueta nodo 4 = [90, 3] 2
30 es el valor acumulado en la etiqueta del nodo de procedencia, en este caso el valor acumulado para el nodo 3. 60 es el valor del arco que une el nodo procedencia (3) y el nodo destino (5). 2 es el número de la iteración.
En este caso, podemos observar que la etiqueta del nodo 4, contiene el menor valor acumulado posible para llegar a este. Así entonces, la etiqueta del nodo 4 pasa a ser permanente.
Tabulamos la iteración 2:
Iteración 3:
En este paso, evaluamos las posibles salidas desde el nodo 4, es decir los nodos 2 y 5. De manera que debemos asignar las etiquetas para cada nodo:
Etiqueta nodo 2 = [valor acumulado, procedencia] iteración
Etiqueta nodo 2 = [40 + 15, 4] 3
Etiqueta nodo 2 = [55, 4] 3
40 es el valor acumulado en la etiqueta del nodo de procedencia, en este caso el valor acumulado para el nodo 4. 15 es el valor del arco que une el nodo procedencia (4) y el nodo destino (2). 3 es el número de la iteración.
Etiqueta nodo 5 = [valor acumulado, procedencia] iteración
Etiqueta nodo 5 = [40 + 50, 4] 3
Etiqueta nodo 5 = [90, 4] 3
40 es el valor acumulado en la etiqueta del nodo de procedencia, en este caso el valor acumulado para el nodo 3. 50 es el valor del arco que une el nodo procedencia (4) y el nodo destino (5). 3 es el número de la iteración.
En este caso, podemos observar que el nodo 2 ahora cuenta con 2 etiquetas temporales, y definitivas, ya que no existe otra ruta hacia dicho nodo. De manera que se elige la etiqueta que tenga el menor valor acumulado. Así entonces, la etiqueta del nodo 2 con procedencia del nodo 4, pasa a ser permanente.
Tabulamos la iteración 3:
Iteración 4:
En este paso, evaluamos las posibles salidas desde el nodo 2 y el nodo 5. Sin embargo, el nodo 2 solo tiene un posible destino, el nodo 3, el cual ya tiene una etiqueta permanente, de manera que no puede ser reetiquetado. Ahora, evaluamos el nodo 5 y es un nodo que no tiene destinos. Así entonces, su etiqueta temporal pasa a ser permanente, en este caso cuenta con 2 etiquetas que tienen el mismo valor, es decir, alternativas óptimas. De esta manera concluye el algortimo de Dijkstra.
¿Cuál es la ruta más corta? La ruta más corta entre el nodo 1 (origen) y cualquier otro nodo de la red (destino), se determina partiendo desde el nodo destino y recorriendo las procedencias de sus etiquetas. Por ejemplo:
¿Cuál es la ruta más corta entre el nodo 1 y el nodo 4?
En este caso, debemos partir desde la etiqueta del nodo 4.
La ruta más corta entre el nodo 1 y el nodo 4 tiene un valor acumulado de: 40
Es necesario considerar, que los valores utilizados en los arcos de la red objeto de estudio del algoritmo de Dijkstra, no necesariamente representan distancias. Si bien, es un modelo que aborda el denominado «problema de la ruta más corta»; en la práctica, puede utilizarse para optimizar: distancia, costos, tiempo.
De hecho, los sistemas de ruteo utilizados en la actualidad, priorizan los costos y el tiempo como variable decisión de los modelos de optimización.
Hola, me gustó mucho el trabajo realizado, actualmente hago una investigación y me gustaría saber de donde sacaron toda su información.
Espero su respuesta.