Algoritmo de la ruta más corta de Dijkstra - Introducción gráfica y detallada
Aprenderás:
• Conceptos básicos de grafos (una introducción breve).
• Aplicaciones del algoritmo de Dijkstra.
• Cómo funciona detrás de escenas con un ejemplo paso a paso.
Comencemos.
Introducción a los grafos
Primero veremos una breve introducción a los grafos.
Conceptos básicos
Los grafos son estructuras de datos usadas para representar "conexiones" entre pares
de elementos.
• Estos elementos se llaman nodos. Representan objetos reales, personas o
entidades.
• Las conexiones entre los nodos se llaman aristas o arcos.
Esta es una representación gráfica de un grafo:
Los nodos se representan como círculos de colores y los arcos se representan como
líneas que conectan los círculos.
Dato: dos nodos están conectados si existe un arco entre ellos.
Aplicaciones
Los grafos se pueden aplicar directamente a escenarios de la vida real. Por ejemplo,
podríamos usar grafos para modelar una red de transporte, en la cual los nodos
representarían instalaciones para enviar o recibir productos y los arcos
representarían caminos que los conectan (como en el siguiente diagrama).
Red representada como un grafo.
Tipos de grafos
Los grafos pueden ser:
• No dirigido: si para cada par de nodos conectados, puedes ir de un nodo al
otro en ambas direcciones.
• Dirigido: si para cada par de nodos conectados, solo puedes ir de un nodo a
otro en una dirección específica. Usamos flechas en lugar de líneas sencillas
para representar arcos dirigidos.
Grafo ponderado
Un grafo ponderado es un grafo cuyos arcos tienen un "peso", "valor", o "costo"
asociado. El valor de cada arco puede representar la distancia, tiempo, u otro valor
que modele la conexión entre el par de nodos que conecta.
Por ejemplo, en el grafo ponderado que tenemos a continuación, puedes ver un
número azul junto a cada arco. Este número representa el valor o costo del arco
correspondiente.
Dato: estos valores son muy importantes para el algoritmo de Dijkstra. Verás por
qué en tan solo un momento.
Introducción al algoritmo de Dijkstra
Ahora que ya conoces los concepts básicos de los grafos, comencemos a ver más
detalles sobre este algoritmo asombroso.
Aprenderás:
• Su propósito y cómo se usa.
• Aspectos básicos del algoritmo.
• Requisitos.
Propósito y Usos
Con el algoritmo de Dijkstra, puedes encontrar la ruta más corta o el camino más
corto entre los nodos de un grafo. Específicamente, puedes encontrar el camino más
corto desde un nodo (llamado el nodo de origen) a todos los otros nodos del grafo,
generando un árbol del camino más corto.
Aspectos básicos del algoritmo de Dijkstra
• El algoritmo de Dijkstra básicamente inicia en el nodo que escojas (el nodo de
origen) y analiza el grafo para encontrar el camino más corto entre ese nodo y
todos los otros nodos en el grafo.
• El algoritmo mantiene un registro de la distancia conocida más corta desde el
nodo de origen hasta cada nodo y actualiza el valor si encuentra un camino
más corto.
• Una vez que el algoritmo ha encontrado el camino más corto entre el nodo de
origen y otro nodo, ese nodo se marca como "visitado" y se agrega al camino.
• El proceso continúa hasta que todos los nodos en el grafo han sido añadidos al
camino. De esta forma, tenemos un camino que conecta al nodo de origen con
todos los otros nodos siguiendo el camino más corto posible para llegar a
cada uno de ellos.
Requisitos
El algoritmo de Dijkstra solo puede aplicarse a grafos con arcos cuyos valores o pesos
son positivos. Esto se debe a que durante es proceso, los valores de los arcos deben
ser sumados para encontrar el camino más corto.
Si existe un valor negativo en el grafo, el algoritmo no funcionará correctamente. Una
vez que el nodo se marca como "visitado", el camino actual hacia ese nodo se marca
como el camino más corto para alcanzar ese nodo pero los valores negativos pueden
cambiar esto si el valor total puede ser reducido luego de este paso.
Ejemplo del algoritmo de Dijkstra
Ahora que ya sabes más sobre este algoritmo, veamos cómo funciona detrás de
escenas con un ejemplo paso a paso.
Tenemos el siguiente grafo:
El algoritmo generará el camino más corto desde el nodo 0 hasta todos los demás
nodos del grafo.
Dato: para este grafo, asumiremos que los valores de los arcos representan la
distancia entre cada par de nodos.
Obtendremos el camino más corto desde el nodo 0 hasta el nodo 1, desde el
nodo 0 hasta el nodo 2, desde el nodo 0 hasta el nodo 3 y así sucesivamente para
cada nodo del grafo.
Inicialmente, tendremos esta lista de distancias (en la siguiente imagen):
• La distancia desde el nodo de origen a sí mismo es 0. En este ejemplo, el nodo
de origen será el nodo 0, pero puede ser cualquier nodo que escojas.
• La distancia desde el nodo de origen a todos los otros nodos del grafo no se ha
calculado todavía, así que usaremos el símbolo de infinito para representar
esto al iniciar el algoritmo.
También tendremos esta lista para mantener un registro de los nodos que todavía no
se han visitado (los que no han sido incluidos en el camino). Los llamaremos "nodos
por visitar":
Dato: Recuerda que el algoritmo se completa cuando todos los nodos han sido
agregados al camino final que conecta al nodo de origen con todos los otros nodos a
través del camino más corto.
Como escogemos iniciar en el nodo 0, podemos marcar este nodo como visitado. Lo
tachamos de la lista de nodos por visitar y añadimos un borde rojo al nodo
correspondiente en el diagrama:
Ahora debemos comenzar a verificar la distancia desde el nodo 0 hasta sus nodos
adyacentes. Como puedes ver, estos nodos son el nodo 1 y el nodo 2 (conectados por
los arcos rojos en el diagrama):
Dato: esto no significa que estamos añadiendo los nodos adyacentes
inmediatamente al camino más corto. Antes de añadir un nodo a este camino,
debemos verificar si ya encontramos el camino más corto para alcanzarlo. Solo
estamos haciendo un proceso de verificación inicial para ver las opciones
disponibles.
Debemos actualizar las distancias desde el nodo 0 hasta el nodo 1 y el nodo 2 con los
valores de los arcos que los conectan con el nodo 0 (el nodo de origen).
Estos valores son, respectivamente:
Después de actualizar las distancias a los nodos adyacentes, debemos:
• Seleccionar el nodo más cercando al nodo de origen en base a las distancias
que conocemos hasta el momento.
• Marcarlo como visitado.
• Añadirlo al camino.
Si verificamos la lista de distancias, podemos ver que el nodo 1 tiene la menor
distancia hasta el nodo de origen (una distancia de 2), así que lo añadimos al camino.
En el diagrama, podemos representar esto con un borde rojo:
Lo marcamos con un cuadrado rojo en la lista para representar que ha sido "visitado"
y que ya hemos encontrado el camino más corto hasta este nodo:
Lo tachamos de la lista de nodos pendientes por visitar:
Ahora tenemos que analizar los nuevos nodos adyacentes para encontrar el camino
más corto para llegar a ellos. Solo analizaremos los nodos que son adyacentes a los
nodos que ya son parte del camino más corto (el camino marcado con arcos rojos).
Los nodos 3 y 2 son adyacentes a los nodos que ya están en el camino porque están
directamente conectados al nodo 1 y al nodo 0, respectivamente (como puedes ver
en el siguiente diagrama). Estos son los nodos que analizaremos en el próximo paso.
Como ya tenemos la distancia desde el nodo de origen al nodo 2 escrita en nuestra
lista, no tenemos que actualizar la distancia esta vez. Solo debemos actualizar la
distancia desde el nodo de origen hasta el nuevo nodo adyacente (el nodo 3).
Esta distancia es 7. Veamos por qué.
Para encontrar la distancia desde el nodo de origen hasta otro nodo (en este caso, el
nodo 3), sumamos los valores de todos los arcos que forman el camino más corto
para alcanzar ese nodo:
• Para el nodo 3: la distancia total es 7 porque sumamos los valores de los
arcos que forman el camino 0 -> 1 -> 3 (2 para el arco 0 -> 1 y 5 para el arco 1 ->
3).
Ahora que ya tenemos la distancia hasta los nodos adyacentes, debemos escoger el
nodo que será añadido al camino más corto. Debemos seleccionar el
nodo pendiente por visitar con la distancia más corta (conocida hasta el momento)
hasta el nodo de origen.
A partir de la lista de distancias, podemos detectar inmediatamente que este nodo es
el nodo 2, con una distancia de 6:
Lo agregamos al camino de forma gráfica con un borde rojo alrededor del nodo y un
arco rojo:
También lo marcamos como visitado agregando un cuadrado rojo pequeño en la lista
de distancias y lo tachamos de la lista de nodos pendientes por visitar.
Ahora tenemos que repetir el proceso para encontrar el camino más corto desde el
nodo de origen hasta el nuevo nodo adyacente, el cual es el nodo 3.
Puedes ver que tenemos dos caminos posibles: 0 -> 1 -> 3 o 0 -> 2 -> 3. Veamos cómo
podemos determinar cuál es el camino más corto.
El nodo 3 ya tiene una distancia en la lista que registramos previamente (7 en la lista
que vemos en la siguiente imagen). Esta distancia fue el resultado de un paso previo
en el cual sumamos los valores 5 y 2 de los dos arcos que necesitamos recorrer para
seguir el camino 0 -> 1 -> 3.
Pero ahora tenemos otra alternativa. Si escogemos seguir el camino 0 -> 2 -> 3,
necesitaríamos recorrer dos arcos 0 -> 2 y 2 -> 3 con valores 6 y 8, respectivamente,
los cual representa una distancia total de 14.
La primera distancia es más corta (7 vs. 14), así que escogeremos mantener el
camino original 0 -> 1 -> 3. Solo actualizamos la distancia si el camino nuevo es
más corto.
Por lo tanto, añadimos este nodo al camino con la primera opción: 0 -> 1 -> 3.
Marcamos este nodo como visitado y lo tachamos de la lista de nodos pendientes por
visitar:
Ahora repitamos el proceso nuevamente.
Debemos verificar los nuevos nodos adyacentes que no hemos visitado hasta el
momento. Esta vez, estos nodos son el nodo 4 y el nodo 5 ya que son adyacentes al
nodo 3.
Actualizamos las distancias entre estos nodos y el nodo de origen, siempre
intentando encontrar el camino más corto, si es posible:
• Para el nodo 4: la distancia es 17 en el camino 0 -> 1 -> 3 -> 4.
• Para el nodo 5: la distancia es 22 en el camino 0 -> 1 -> 3 -> 5.
Dato: nota que solo podemos considerar extender el camino más corto (marcado
en rojo). No podemos considerar caminos que nos llevan a través de arcos que no
han sido añadidos al camino más corto (por ejemplo, no podemos usar un camino
que atraviese el arco 2 -> 3).
Debemos escoger el nodo pendiente por visitar que ahora será marcado como
visitado. En este caso, este el nodo 4 porque tiene la distancia más corta de la lista de
distancias.
Lo agregamos de forma gráfica al diagrama:
También lo marcamos como "visitado" agregando un cuadrado rojo pequeño en la
lista:
Y lo tachamos de la lista de nodos pendientes por visitar:
Repetimos el proceso nuevamente.
Verificamos los nodos adyacentes: el nodo 5 y el nodo 6. Debemos analizar cada
camino posible que podemos seguir para alcanzarlos a partir de nodos que ya han
sido marcados como visitados y que ya han sido agregados al camino.
Para el nodo 5:
• La primera opción es seguir el camino 0 -> 1 -> 3 -> 5, el cual tiene una
distancia de 22 desde el nodo de origen (2 + 5 + 15). Esta distancia ya se
registró en la lista de distancias en un paso previo.
• La segunda opción sería seguir el camino 0 -> 1 -> 3 -> 4 -> 5, el cual tiene una
distancia de 23 a partir del nodo de origen (2 + 5 + 10 + 6).
El primer camino es más corto, así que lo escogemos para el nodo 5.
Para el nodo 6:
• El camino que podemos seguir es 0 -> 1 -> 3 -> 4 -> 6, el cual tiene una
distancia de 19 a partir del nodo de origen (2 + 5 + 10 + 2).
Marcamos el nodo con la menor distancia que conocemos hasta el momento como
"visitado." En este caso, el nodo 6.
Y lo tachamos de la lista de nodos pendientes por visitar:
Ahora tenemos este camino (marcado en rojo):
Solo nos falta un nodo que no ha sido visitado, el nodo 5. Veamos cómo podemos
incluirlo en el camino.
Existen tres posibles caminos que podemos escoger para alcanzar el nodo 5 a partir
de los nodos que hemos añadido al camino:
• Opción 1: 0 -> 1 -> 3 -> 5 con una distancia de 22 (2 + 5 + 15).
• Opción 2: 0 -> 1 -> 3 -> 4 -> 5 con una distancia de 23 (2 + 5 + 10 + 6).
• Opción 3: 0 -> 1 -> 3 -> 4 -> 6 -> 5 con una distancia de 25 (2 + 5 + 10 + 2 + 6).
Seleccionamos el camino más corto: 0 -> 1 -> 3 -> 5 con una distancia de 22.
Marcamos el nodo como "visitado" y lo tachamos de la lista de nodos pendientes por
visitar:
Y voilà! Tenemos el resultado final con el camino más corto desde el nodo 0 hasta
cada nodo del grafo.
En el diagrama, las líneas rojas indican los arcos que pertenecen al camino más
corto. Debes seguir estos arcos para seguir el camino más corto para alcanzar un
nodo en el grafo, si inicias el recorrido desde el nodo 0.
Por ejemplo, si quieres llegar al nodo 6 iniciando desde el nodo 0, solo necesitas
seguir los arcos rojos y estarás siguiendo el camino más corto automáticamente (0 ->
1 -> 3 -> 4 - > 6).
En resumen
• Los grafos son usados para modelar conexiones entre objetos, personas o
entidades. Tienen dos elementos principales: nodos y arcos. Los nodos
representan objetos y los arcos representan las conexiones entre esos
objetos.
• El algoritmo de Dijkstra encuentra el camino más corto entre un nodo dado (el
nodo de origen) y todos los otros nodos del grafo.
• Este algoritmo usa los valores de los arcos para encontrar el camino que
minimiza el valor total entre el nodo de origen y los demás nodos del grafo.
Este valor depende de lo que representa el valor de los arcos en el grafo. Puede
ser, por ejemplo, tiempo, costo o distancia.
