¡Bienvenidos! Si siempre ha querido aprender y comprender el algoritmo de Dijkstra, este artículo es para usted. Verás cómo funciona entre bastidores con una explicación gráfica paso a paso.
Aprenderás:
- Conceptos básicos de gráficos (una revisión rápida).
- Para qué se utiliza el algoritmo de Dijkstra.
- Cómo funciona entre bastidores con un ejemplo paso a paso.
Vamos a empezar. ✨
? Introducción a los gráficos
Comencemos con una breve introducción a los gráficos.
Conceptos básicos
Los gráficos son estructuras de datos que se utilizan para representar "conexiones" entre pares de elementos.
- Estos elementos se denominan nodos . Representan objetos, personas o entidades de la vida real.
- Las conexiones entre nodos se denominan bordes .
Esta es una representación gráfica de un gráfico:
Los nodos se representan con círculos de colores y los bordes se representan con líneas que conectan estos círculos.
? Sugerencia: Dos nodos están conectados si hay un borde entre ellos.
Aplicaciones
Los gráficos son directamente aplicables a escenarios del mundo real. Por ejemplo, podríamos usar gráficos para modelar una red de transporte donde los nodos representarían instalaciones que envían o reciben productos y los bordes representan caminos o caminos que los conectan (ver más abajo).
Tipos de gráficos
Los gráficos pueden ser:
- Sin dirección: si por cada par de nodos conectados, puede pasar de un nodo a otro en ambas direcciones.
- Dirigido: si por cada par de nodos conectados, solo se puede ir de un nodo a otro en una dirección específica. Usamos flechas en lugar de líneas simples para representar bordes dirigidos.
? Consejo: en este artículo trabajaremos con gráficos no dirigidos.
Gráficos ponderados
Un gráfico de peso es un gráfico cuyos bordes tienen un "peso" o un "costo". El peso de un borde puede representar la distancia, el tiempo o cualquier cosa que modele la "conexión" entre el par de nodos que conecta.
Por ejemplo, en el siguiente gráfico ponderado, puede ver un número azul junto a cada borde. Este número se utiliza para representar el peso del borde correspondiente.
? Consejo: Estos pesos son esenciales para el algoritmo de Dijkstra. Verás por qué en un momento.
? Introducción al algoritmo de Dijkstra
Ahora que conoce los conceptos básicos de los gráficos, comencemos a sumergirnos en este increíble algoritmo.
- Propósito y casos de uso
- Historia
- Conceptos básicos del algoritmo
- Requisitos
Propósito y casos de uso
Con el algoritmo de Dijkstra, puede encontrar la ruta más corta entre los nodos en un gráfico. En particular, puede encontrar la ruta más corta desde un nodo (llamado "nodo de origen") a todos los demás nodos en el gráfico , produciendo un árbol de ruta más corta.
Este algoritmo se utiliza en dispositivos GPS para encontrar el camino más corto entre la ubicación actual y el destino. Tiene amplias aplicaciones en la industria, especialmente en dominios que requieren modelado de redes.
Historia
Este algoritmo fue creado y publicado por el Dr. Edsger W. Dijkstra, un brillante informático e ingeniero de software holandés.
En 1959, publicó un artículo de 3 páginas titulado "Una nota sobre dos problemas relacionados con los gráficos", donde 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 de Rotterdam a Groningen? Es el algoritmo para el camino más corto, que diseñé en unos 20 minutos. Una mañana estaba de compras en Ámsterdam con mi joven prometida y, cansado, nos sentamos en la terraza del café a tomar una taza de café y estaba pensando en si podía hacer esto, y luego diseñé el algoritmo para el camino más corto. . Como dije, fue un invento de 20 minutos. De hecho, se publicó en 1959, tres años después. La publicación sigue siendo bastante agradable. Una de las razones por las que es tan bonito es que lo diseñé sin lápiz ni papel. Sin lápiz y papel, está casi obligado a evitar todas las complejidades evitables. Con el tiempo, ese algoritmo se convirtió, para mi gran asombro, en una de las piedras angulares de mi fama. - Como se cita en el artículo Edsger W.Dijkstra de una entrevista con Edsger W. Dijkstra.⭐ Increíble, ¿verdad? En solo 20 minutos, el Dr. Dijkstra diseñó uno de los algoritmos más famosos de la historia de la informática.
Conceptos básicos del algoritmo de Dijkstra
- El algoritmo de Dijkstra básicamente comienza en el nodo que elija (el nodo de origen) y analiza el gráfico para encontrar la ruta más corta entre ese nodo y todos los demás nodos del gráfico.
- El algoritmo realiza un seguimiento de la distancia más corta conocida actualmente desde cada nodo al nodo de origen y actualiza estos valores si encuentra una ruta más corta.
- Una vez que el algoritmo ha encontrado la ruta más corta entre el nodo de origen y otro nodo, ese nodo se marca como "visitado" y se agrega a la ruta.
- El proceso continúa hasta que todos los nodos del gráfico se hayan agregado a la ruta. De esta manera, tenemos una ruta que conecta el nodo de origen con todos los demás nodos siguiendo la ruta más corta posible para llegar a cada nodo.
Requisitos
El algoritmo de Dijkstra solo puede funcionar con gráficos que tengan pesos positivos . Esto se debe a que, durante el proceso, se deben sumar los pesos de los bordes para encontrar el camino más corto.
Si hay un peso negativo en el gráfico, el algoritmo no funcionará correctamente. Una vez que un nodo ha sido marcado como "visitado", la ruta actual a ese nodo se marca como la ruta más corta para llegar a ese nodo. Y los pesos negativos pueden alterar esto si se puede disminuir el peso total después de que se haya producido este paso.
? Ejemplo de algoritmo de Dijkstra
Ahora que sabe más sobre este algoritmo, veamos cómo funciona entre bastidores con un ejemplo paso a paso.
Tenemos este gráfico:
El algoritmo generará la ruta más corta desde el nodo 0hasta todos los demás nodos del gráfico.
? Consejo: Para este gráfico, asumiremos que el peso de los bordes representa la distancia entre dos nodos.
Tendremos la ruta más corta de nodo 0a nodo 1, de nodo 0a nodo 2, de nodo 0a nodo 3, y así sucesivamente para cada nodo en el gráfico.
Inicialmente, tenemos esta lista de distancias (consulte la lista a continuación):
- La distancia desde el nodo de origen hasta sí mismo es
0. Para este ejemplo, el nodo de origen será un nodo,0pero puede ser cualquier nodo que elija. - La distancia desde el nodo de origen a todos los demás nodos aún no se ha determinado, por lo que usamos el símbolo de infinito para representar esto inicialmente.
También tenemos esta lista (ver más abajo) para realizar un seguimiento de los nodos que aún no se han visitado (nodos que no se han incluido en la ruta):
? Consejo: recuerde que el algoritmo se completa una vez que se han agregado todos los nodos a la ruta.
Como elegimos comenzar en el nodo 0, podemos marcar este nodo como visitado. De manera equivalente, lo tachamos de la lista de nodos no visitados y agregamos un borde rojo al nodo correspondiente en el diagrama:
Ahora debemos comenzar a verificar la distancia desde el nodo 0hasta sus nodos adyacentes. Como puede ver, estos son nodos 1y 2(vea los bordes rojos):
? Sugerencia: Esto no significa que estemos agregando inmediatamente los dos nodos adyacentes al camino más corto. Antes de agregar un nodo a esta ruta, debemos verificar si hemos encontrado la ruta más corta para llegar a él. Simplemente estamos haciendo un proceso de examen inicial para ver las opciones disponibles.
Necesitamos actualizar las distancias de nodo 0a nodo 1y nodo 2con los pesos de los bordes que los conectan al nodo 0(el nodo de origen). Estos pesos son 2 y 6, respectivamente:
Después de actualizar las distancias de los nodos adyacentes, necesitamos:
- Seleccione el nodo más cercano al nodo de origen en función de las distancias conocidas actuales.
- Márcalo como visitado.
- Agréguelo a la ruta.
Si revisamos la lista de distancias, podemos ver que el nodo 1tiene la distancia más corta al nodo de origen (una distancia de 2), por lo que lo agregamos a la ruta.
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 hemos encontrado la ruta más corta a este nodo:
Lo tachamos de la lista de nodos no visitados:
Ahora necesitamos analizar los nuevos nodos adyacentes para encontrar el camino más corto para llegar a ellos. Solo analizaremos los nodos que están adyacentes a los nodos que ya forman parte del camino más corto (el camino marcado con bordes rojos).
El nodo 3y el nodo 2son adyacentes a los nodos que ya están en la ruta porque están conectados directamente al nodo 0y al nodo 1, respectivamente, como puede ver a continuación. Estos son los nodos que analizaremos en el siguiente paso.
Dado que ya tenemos la distancia desde el nodo de origen al nodo 2escrito en nuestra lista, no necesitamos actualizar la distancia esta vez. Solo necesitamos actualizar la distancia desde el nodo de origen al nuevo nodo adyacente (nodo 3):
Esta distancia es 7 . Veamos por qué.
Para encontrar la distancia desde el nodo fuente a otro nodo (en este caso, nodo 3), agregamos los pesos de todos los bordes que forman la ruta más corta para llegar a ese nodo:
- Para nodo
3: la distancia total es 7 porque sumamos los pesos de los bordes que forman el camino0 -> 1 -> 3(2 para el borde0 -> 1y 5 para el borde1 -> 3).
Ahora que tenemos la distancia a los nodos adyacentes, tenemos que elegir qué nodo se agregará a la ruta. Debemos seleccionar el nodo no visitado con la distancia más corta (conocida actualmente) al nodo de origen.
De la lista de distancias, podemos detectar inmediatamente que este es un nodo 2con distancia 6 :
Lo agregamos a la ruta gráficamente con un borde rojo alrededor del nodo y un borde rojo:
También lo marcamos como visitado agregando un pequeño cuadrado rojo en la lista de distancias y tachándolo de la lista de nodos no visitados:
Ahora tenemos que repetir el proceso para encontrar la ruta más corta desde el nodo de origen al nuevo nodo adyacente, que es el nodo 3.
Puedes ver que tenemos dos caminos posibles 0 -> 1 -> 3o 0 -> 2 -> 3. Veamos cómo podemos decidir cuál es el camino más corto.
El nodo 3ya tiene una distancia en la lista que se registró anteriormente ( 7, consulte la lista a continuación). Esta distancia fue el resultado de un paso anterior, donde sumamos los pesos 5 y 2 de los dos bordes que necesitábamos cruzar para seguir el camino 0 -> 1 -> 3.
Pero ahora tenemos otra alternativa. Si optamos por seguir el camino 0 -> 2 -> 3, tendríamos que seguir dos aristas 0 -> 2y 2 -> 3con pesos 6 y 8 ,respectivamente,que representa una distancia total de 14 .
Claramente, la primera distancia (existente) es más corta (7 vs 14), por lo que optaremos por mantener el camino original 0 -> 1 -> 3. Solo actualizamos la distancia si el nuevo camino es más corto.
Por lo tanto, añadimos a este nodo de la ruta utilizando la primera alternativa: 0 -> 1 -> 3.
Marcamos este nodo como visitado y lo tachamos de la lista de nodos no visitados:
Ahora repetimos el proceso nuevamente.
Necesitamos comprobar los nuevos nodos adyacentes que no hemos visitado hasta ahora. Esta vez, estos nodos son nodo 4y nodo, 5ya que son adyacentes al nodo 3.
Actualizamos las distancias de estos nodos al nodo fuente, siempre intentando encontrar una ruta más corta, si es posible:
- Para nodo
4: la distancia es 17 desde el camino0 -> 1 -> 3 -> 4. - Para nodo
5: la distancia es 22 desde la ruta0 -> 1 -> 3 -> 5.
? Sugerencia: Tenga en cuenta que solo podemos considerar extender el camino más corto (marcado en rojo). No podemos considerar caminos que nos llevarán a través de bordes que no se han agregado al camino más corto (por ejemplo, no podemos formar un camino que pase por el borde 2 -> 3).
Necesitamos elegir qué nodo no visitado se marcará como visitado ahora. En este caso, es un nodo 4porque tiene la distancia más corta en la lista de distancias. Lo agregamos gráficamente en el diagrama:
También lo marcamos como "visitado" agregando un pequeño cuadrado rojo en la lista:
Y lo tachamos de la lista de nodos no visitados:
Y repetimos el proceso nuevamente. Comprobamos los nodos adyacentes: nodo 5y nodo 6. Necesitamos analizar cada posible camino que podemos seguir para llegar a ellos desde nodos que ya han sido marcados como visitados y agregados al camino.
Para nodo 5:
- La primera opción es seguir la ruta
0 -> 1 -> 3 -> 5, que 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 anterior. - La segunda opción sería seguir la ruta
0 -> 1 -> 3 -> 4 -> 5, que tiene una distancia de 23 desde el nodo de origen (2 + 5 + 10 + 6).
Claramente, la primera ruta es más corta, por lo que la elegimos para node 5.
Para nodo 6:
- La ruta disponible es
0 -> 1 -> 3 -> 4 -> 6, que tiene una distancia de 19 desde el nodo de origen (2 + 5 + 10 + 2).
Marcamos el nodo con la distancia más corta (conocida actualmente) como visitado. En este caso, node 6.
Y lo tachamos de la lista de nodos no visitados:
Ahora tenemos este camino (marcado en rojo):
Aún no se ha visitado un solo nodo, node 5. Veamos cómo podemos incluirlo en la ruta.
Hay tres rutas diferentes que podemos tomar para llegar al nodo 5desde los nodos que se han agregado a la ruta:
- 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 -> 5con una distancia de 22 .
Marcamos el nodo como visitado y lo tachamos de la lista de nodos no visitados:
¡Y voilá! Tenemos el resultado final con la ruta más corta de nodo 0a cada nodo en el gráfico.
En el diagrama, las líneas rojas marcan los bordes que pertenecen al camino más corto. Debe seguir estos bordes para seguir el camino más corto para llegar a un nodo dado en el gráfico comenzando desde el nodo 0.
Por ejemplo, si desea llegar al nodo 6comenzando desde el nodo 0, solo debe seguir los bordes rojos y seguirá el camino más corto 0 -> 1 -> 3 -> 4 - > 6automáticamente.
? En resumen
- Los gráficos se utilizan para modelar conexiones entre objetos, personas o entidades. Tienen dos elementos principales: nodos y bordes. Los nodos representan objetos y los bordes representan las conexiones entre estos objetos.
- El algoritmo de Dijkstra encuentra la ruta más corta entre un nodo dado (que se llama "nodo de origen") y todos los demás nodos en un gráfico.
- Este algoritmo utiliza los pesos de los bordes para encontrar la ruta que minimiza la distancia total (peso) entre el nodo de origen y todos los demás nodos.
Realmente espero que les haya gustado mi artículo y les haya resultado útil. Ahora sabe cómo funciona el algoritmo de Dijkstra entre bastidores. Sígueme en Twitter @EstefaniaCassN y mira mis cursos en línea.