¡Hola! Si siempre has querido aprender cómo funciona el algoritmo de Dijkstra, este artículo es para ti. Entenderás cómo funciona detrás de escenas con una explicación gráfica paso a paso.
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).
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.
💡 Dato: en este artículo, trabajaremos con grafos no 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.
- Su historia.
- 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.
Este algoritmo es usado por los dispositivos GPS para encontrar el camino más corto entre la ubicación actual y el destino del usuario. Tiene amplias aplicaciones en la industria, especialmente en aquellas áreas que requieren modelar redes.
Historia
Fue creado y publicado por el Dr. Edsger W. Dijkstra, un científico Neerlandés brillante en ciencias de la computación e ingeniería de software.
En 1959, publicó un artículo de tres páginas titulado: "A note on two problems in connexion with graphs", lo cual se traduce a español como "Una nota sobre dos problemas relacionados con grafos." En este artículo explicó su nuevo algoritmo.
Durante una entrevista en 2001, el Dr. Dijkstra reveló cómo y por qué diseñó el algoritmo:
¿Cuál es el camino más corto para viajar desde Rotterdam a Groningen? Es el algoritmo para el camino más corto, el cual diseñé en aproximadamente 20 minutos. Una mañana estaba comprando en Amsterdam con mi joven prometida, y cansados, nos sentamos en una terraza de un café para beber una taza de café y estaba pensando cómo podría hacerlo, y luego diseñé el algoritmo para el camino más corto. Como acabo de mencionar, fue un invento de 20 minutos. De hecho, fue publicado en 1959, tres años más tarde. La publicación sigue siendo bastante buena. Una de las razones de por qué es tan buena es que la diseñé casi sin lápiz ni papel. Sin lápiz ni papel no tienes otra opción más que evitar todas las complejidades que se puedes evitar. Con el tiempo, ese algoritmo se convirtió, para mi sorpresa, en una de las piedras angulares de mi fama. - Cita de Edsger W. Dijkstra en el artículo An interview with Edsger W. Dijkstra.
Texto original en inglés:
What’s the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path, which I designed in about 20 minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a 20-minute invention. In fact, it was published in 1959, three years later. The publication is still quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. Without pencil and paper you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame. — As quoted in the article Edsger W. Dijkstra from An interview with Edsger W. Dijkstra.
⭐ Increíble, ¿cierto? En tan solo 20 minutos, el Dr. Dijkstra diseñó uno de los algoritmos más famosos de la historia de la ciencia de la computación.
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 nodo0, 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 camino0 -> 1 -> 3(2 para el arco0 -> 1y 5 para el arco1 -> 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 camino0 -> 1 -> 3 -> 4. - Para el nodo
5: la distancia es 22 en el camino0 -> 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 -> 5con una distancia de 22 (2 + 5 + 15). - Opción 2:
0 -> 1 -> 3 -> 4 -> 5con una distancia de 23 (2 + 5 + 10 + 6). - Opción 3:
0 -> 1 -> 3 -> 4 -> 6 -> 5con 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.
Espero que te haya gustado mi tutorial y que te haya sido de utilidad. Te invito a seguirme en Twitter (@EstefaniaCassN). ⭐