El Algoritmo de Dijkstra

El Algoritmo de Dijkstra o de Caminos mínimos

El algoritmo de Dijkstra (o de caminos mínimos) es un algoritmo voraz para la determinación del camino más corto de un grafo.

Puede parecer una definición un tanto complicada con lo de voraz y grafo, pero vamos a explicarlo paso a paso:

¿Qué es un grafo?

Un grafo es una colección de nodos o vértices unidos por líneas o aristas. Se usa para representar relaciones binarias entre los elementos.

Voy a saltarme las nociones matemáticas, dando nociones simples para entender el problema en cuestión. Puedes encontrar más información en aquí.

Imagina que los nodos son ciudades y que cada una de ellas tiene un aeropuerto. Se puede ir de una ciudad a otra si la aerolínea ha creado una ruta. Esa ruta tiene un coste, bien sea kilómetros o coste total de ir en avión a esa ciudad.

Pues bien, esos datos se pueden simplificar con un grafo dirigido ponderado, como el que se indica a continuación:

En el grafo, un nodo seria la ciudad, cada una de las aristas las diferentes rutas disponibles y el valor de la arista el coste de ir de una ciudad a otra.

El algoritmo de Dijkstra se basa en estas estructuras para la resolución del problema del camino más corto de un nodo a otro. En el caso de no estar ponderadas las aristas, se suele dar el valor de 1.

¿Qué es un algoritmo voraz?

El esquema voraz (greedy algorithms) se aplica a problemas de optimización en los que la solución se puede construir paso a paso sin necesidad de reconsiderar decisiones ya tomadas. Genéricamente el problema que se puede resolver con este tipo de esquema es: encontrar un conjunto de candidatos que constituya una solución y que optimice una función objetivo. Este esquema se utiliza principalmente en problemas de planificación de tareas y en problemas que se pueden modelar con grafos, en los que hay que realizar una búsqueda, cálculo de recorridos u optimización de pesos, entre otras tareas.

Los problemas que se pueden resolver con este esquema constan de n candidatos y se trata de encontrar una solución basada en hallar un subconjunto de esos candidatos, o una secuencia ordenada de los mismos, de manera que se optimice (maximice o minimice) una función objetivo. En este esquema se trabaja por etapas, considerando la elección de un candidato en cada etapa. Habrá que seleccionar en cada una el candidato más prometedor de los aún disponibles y decidir si se incluye o no en la solución.

Si quieres profundizar más sobre los algoritmos voraces, dispones de más información aquí.

¿Qué es el algoritmo de Dijkstra?

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de coste negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

Este algoritmo utiliza dos conjuntos de nodos, S y C. S contiene los nodos ya seleccionados y cuya distancia mínima al origen ya se conoce y C contiene los demás nodos, C = N \ S, aquellos cuya distancia mínima al origen no se conoce todavía. Al inicio del algoritmo S sólo contiene el nodo origen y cuando finaliza el algoritmo contiene todos los nodos del grafo y además se conocen las longitudes mínimas desde el origen a cada uno de ellos. La función de selección elegirá en cada paso el nodo de C cuya distancia al origen sea mínima.

El algoritmo de Dijkstra utiliza la noción de camino especial. Un camino desde el nodo origen hasta otro nodo es especial si todos los nodos intermedios del camino pertenecen a S, es decir, se conoce el camino mínimo desde el origen a cada uno de ellos. Hará falta un array, especial[], que en cada paso del algoritmo contendrá la longitud del camino especial más corto (si el nodo está en S), o el camino más corto conocido (si el nodo está en C) que va desde el origen hasta cada nodo del grafo. Cuando se va a añadir un nodo a S, el camino especial más corto hasta ese nodo es también el más corto de todos los caminos posibles hasta él. Cuando finaliza el algoritmo todos los nodos están en S y por lo tanto todos los caminos desde el origen son caminos especiales.

Las longitudes o distancias mínimas que se esperan calcular con el algoritmo estarán almacenadas en el array especial[].

Se supone que los nodos están numerados de $1$ a $n$, por lo que N = {1, 2,  ...  , n}, y que el nodo 1 es el nodo origen. También se supone que la función Distancia() devolverá la distancia o coste entre los dos nodos que son sus argumentos. Si existe una arista entre dichos nodos devolverá la etiqueta o peso asociado, en caso de que no exista una arista devolverá un valor representativo o suficientemente grande, por ejemplo ∞.

tipo VectorNat = matriz[O..n] de natural

fun Dijkstra (G = <N,A>: grafo): VectorNat, VectorNat

   var

      especial, predecesor: VectorNat

      C: conjunto de nodos

   fvar

   C={2,3,...,n}

   para i = 2 hasta n hacer

      especial[i] = Distancia(1 ,i)

      predecesor[i] = 1

   fpara

   mientras C contenga más de 1 nodo hacer

      v = nodo en C que minimiza especial[v]

      C = C\{v}

      para cada w en C hacer

         si especial[w] > especial[v] + Distancia(v,w) entonces

            especial[w] = especial[v] + Distancia(v,w)

            predesecor[w] = v

         fsi

      fpara

   fmientras

   dev especial[],predecesor[]

ffun

Ejemplo de ejecución:

Si quieres profundizar más sobre los algoritmos voraces, dispones de más información aquí,

El ejemplo del robot desplazándose por un circuito

Sea un robot R que dispone de una batería de N unidades de energía y se encuentra en un circuito por el que puede desplazarse. El objetivo es que R se desplace desde el punto en el que se encuentra hasta el punto de salida S del circuito, contando con que en el camino se puede encontrar con obstáculos, O, que son infranqueables. El paso por una casilla franqueable supone un gasto de energía igual al valor que indica la casilla, que deberá ser mayor que 0. Se busca un algoritmo que permita al robot llegar al punto S gastando el mínimo de energía.

El circuito se puede representar mediante una matriz de dimensiones n x m en la que desde cada elemento se puede acceder a un elemento adyacente con el consumo de energía que indique la casilla. En el apartado 3.8 del texto base se puede ver un ejemplo detallado de un circuito concreto. El esquema que se utilizará para su resolución será el indicado en el texto base para este problema: esquema voraz, en particular la solución basada en el algoritmo de Dijkstra.

Aplicación del algoritmo Dijkstra

El tablero o circuito se puede modelar como un grafo en el que cada casilla es un nodo y el contenido de la casilla el coste energético de acceder a dicho nodo por alguna de sus aristas incidentes. El grafo resultante es dirigido y por lo tanto la matriz no es simétrica.

Para un tablero de 5 x 5, los nodos se han numerado del 1 al 25 empezando por la posición (1,1) del tablero, siguiendo por la (1,2), (1,3),...hasta la (5,5). Dada una posición (i,j) del tablero, le corresponde el número de nodo (i - 1) x 5 + j. En la posición del tablero en el que está el robot R, el coste de acceder a ella desde un nodo que no sea un obstáculo es 0, ya que no se indica otro posible coste, lo mismo ocurre con la posición S.

Con esta representación, el problema se reduce a encontrar un camino de coste mínimo desde la posición en la que se encuentra el robot, R, hasta la posición R. Este problema se puede solucionar utilizando el algoritmo de Dijkstra para calcular la longitud del camino mínimo que va desde el origen hasta el resto de los nodos del grafo. En este caso, el algoritmo Dijkstra se detendrá una vez que el camino hasta el nodo S ya se haya calculado, obteniendo así la ruta de coste mínimo en el camino de R a S.

El algoritmo de Dijkstra adaptado a este problema es el siguiente:

tipo VectorNat = matriz[O..n] de natural

fun Dijkstra (G = <N,A>: grafo, R: natural, S: natural): VectorNat, VectorNat

   var

      especial, predecesor: VectorNat

      C: conjunto de nodos

   fvar

   C={1,2,3,...,n} excepto R

   para i = 1 hasta n y i ≠ R hacer

      especial[i] = Distancia(R ,i)

      predecesor[i] = R

   fpara

   mientras C contenga al nodo S hacer

      v = nodo en C que minimiza especial[v]

      C = C\{v}

      si v ≠ S entonces

         para cada w en C hacer

            si especial[w] > especial[v] + Distancia(v,w) entonces

               especial[w] = especial[v] + Distancia(v,w)

               predesecor[w] = v

            fsi

         fpara

      fsi

   fmientras

   dev especial[],predecesor[]

ffun

Para finalizar

Este ejemplo se ha desarrollado en Java para un trabajo de la asignatura de Programación y Estructuras De Datos Avanzadas del grado en Ingeniería Informática de la UNED.

Os adjunto el proyecto realizado en Java con la solución del problema junto con la memoria que he entregado en su día en el siguiente enlace.

¡Nos vemos Más allá del 0 y del 1!

Atentamente:

Carlos Caride Santeiro