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 $\infty$.
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
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 \times 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) \times 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$.