Encontrar el camino más corto, con un poco de ayuda de Dijkstra

¡Encontrar el camino más corto, con un poco de ayuda de Dijkstra!

Si pasa suficiente tiempo leyendo sobre programación o ciencias de la computación, existe una buena posibilidad de que encuentre las mismas ideas, términos, conceptos y nombres, una y otra vez. Algunos de ellos comienzan a familiarizarse con el tiempo. Naturalmente, orgánicamente y, a veces, sin demasiado esfuerzo de su parte, comienza a aprender qué significan todas estas cosas. Esto sucede porque o has empezado a comprender lentamente el concepto, o has leído sobre una frase tantas veces que comienzas a comprender realmente su significado.

Sin embargo, hay algunas ideas y definiciones que son mucho más difíciles de entender. Estas son las que sientes que se supone que debes saber, pero no lo has encontrado lo suficiente como para comprenderlo realmente.

Los temas que creemos que debemos saber, pero que nunca aprendimos, son los más intimidantes de todos. La barrera de entrada es muy alta, y puede resultar increíblemente difícil de entender algo para lo que no tienes mucho contexto. Para mí, ese tema intimidante es el algoritmo de Dijkstra. Siempre lo había escuchado mencionar de pasada, pero nunca lo encontré, así que nunca tuve el contexto o las herramientas para tratar de entenderlo.

Afortunadamente, en el curso de escribir esta serie, todo eso ha cambiado. Después de años de miedo y ansiedad sobre el algoritmo de Dijkstra, finalmente he llegado a comprenderlo. Y con suerte, al final de esta publicación, ¡tú también lo harás!

Gráficos que pesan mucho en tu mente

Antes de que realmente podamos entrar en el algoritmo súper famoso de Dijkstra, primero debemos recoger algunas semillas de información importante que necesitaremos en el camino.

A lo largo de esta serie, hemos construido lentamente sobre nuestra base de conocimiento de diferentes estructuras de datos. No solo hemos aprendido sobre varios algoritmos de recorrido de gráficos, sino que también nos hemos enseñado los fundamentos de la teoría de gráficos, así como los aspectos prácticos de representar gráficos en nuestro código. Ya sabemos que los gráficos pueden ser dirigidos o no dirigidos, e incluso pueden contener ciclos. También hemos aprendido cómo podemos usar la búsqueda por amplitud y la búsqueda por profundidad para atravesarlas, usando dos estrategias muy diferentes.

En nuestro viaje para comprender los gráficos y los diferentes tipos de estructuras de gráficos que existen, hay un tipo de gráfico que hemos logrado omitir, hasta ahora, eso es. ¡Es hora de que finalmente nos encontremos cara a cara con el gráfico ponderado!

Gráfico ponderado: una definición

Un gráfico ponderado es interesante porque tiene poco que ver con si el gráfico está dirigido, no dirigido o si contiene ciclos. En esencia, un gráfico ponderado es un gráfico cuyos bordes tienen algún tipo de valor asociado con ellos. El valor que se adjunta a un borde es lo que le da al borde su "peso".

El peso de un borde representa el costo o la distancia entre dos nodos.

Una forma común de referirse al "peso" de un solo borde es considerarlo como el costo o la distancia entre dos nodos. En otras palabras, ir del nodo a al nodo b tiene algún tipo de costo.

O, si pensamos en los nodos como ubicaciones en un mapa, entonces el peso podría ser la distancia entre los nodos a y b. Continuando con la metáfora del mapa, el "peso" de un borde también puede representar la capacidad de lo que se puede transportar, o lo que se puede mover entre dos nodos, ay b.

Por ejemplo, en el ejemplo anterior, podríamos determinar que el costo, la distancia o la capacidad entre los nodos c y b se ponderan en 8.

Podemos representar gráficos ponderados usando una lista de adyacencia.

La ponderación de los bordes es lo único que diferencia los gráficos ponderados de los gráficos no ponderados con los que hemos trabajado hasta ahora en esta serie.

De hecho, ¡probablemente ya podamos imaginar cómo representaríamos uno de estos gráficos ponderados! Un gráfico ponderado se puede representar con una lista de adyacencia, con una propiedad adicional: un campo para almacenar el costo / peso / distancia de cada borde en el gráfico. Según nuestra investigación previa sobre la representación gráfica, recordaremos que los bordes de un gráfico en una lista de adyacencia viven en la parte de la "lista".

Para cada borde en nuestro gráfico, modificaremos la definición de la lista vinculada que contiene los bordes para que cada elemento en la lista vinculada pueda contener dos valores, en lugar de solo uno. Estos dos valores serán el índice del nodo opuesto, que es cómo sabemos dónde se conecta este borde, así como el peso asociado con el borde.

Así es como se vería ese mismo gráfico ponderado de ejemplo en formato de lista de adyacencia.

Gráfico ponderado como una lista de adyacencia.

De inmediato, notaremos dos cosas sobre esta representación gráfica: primero, dado que es un gráfico no dirigido, el borde entre los nodos a y b aparecerá dos veces, una en la lista de bordes para el nodo a y otra en la lista de bordes para el nodo b. En segundo lugar, en ambos casos que este borde está representado en la lista de bordes respectiva de cualquiera de los nodos, hay un costo / peso que se almacena en el elemento de la lista vinculada que contiene la referencia al nodo vecino (en este caso, ao b).

Bien, entonces no hay nada demasiado salvaje que necesitemos entender aún, ¿verdad?

Aquí es donde el peso de un gráfico comienza a complicar un poco las cosas:

encontrar el camino más corto entre dos nodos se vuelve mucho más complicado cuando tenemos que tener en cuenta el peso de los bordes por los que atravesamos.

Echemos un vistazo a un ejemplo, y esto comenzará a ser más claro. En el gráfico simple dirigido y ponderado a continuación, tenemos un gráfico con tres nodos (a, byc), con tres bordes dirigidos y ponderados.

¿Cuál es el camino más corto entre los nodos A y B?

Mirando este gráfico, podríamos determinar rápidamente, sin dudarlo, la forma más rápida de llegar del nodo a al nodo b. Hay un límite entre ayb, por lo que debe ser la forma más rápida, ¿verdad?

Bueno no exactamente. Teniendo en cuenta el peso de estos bordes, echemos un segundo vistazo más profundo. Si tomamos la ruta del nodo a al nodo b, nos “costará” 5. Sin embargo, si tomamos la ruta del nodo a al nodo c al nodo b, entonces nos costará solo 3.

¿Pero por qué 3? Bueno, aunque intuitivamente pueda parecer una ruta más larga, si sumamos los bordes de ir del nodo ac y luego del nodo c a b, veremos que el costo total termina en 2 + 1, que es 3. Puede significar que estamos viajando a través de dos bordes, ¡pero un costo de 3 es ciertamente preferible a un costo de 5!

En nuestro gráfico de ejemplo de tres nodos, podríamos ver con bastante facilidad las dos rutas posibles entre nuestros nodos de origen y destino. Sin embargo, ¿qué pasaría si nuestro gráfico fuera mucho más grande, digamos veinte nodos? No habría sido tan fácil para nosotros encontrar el camino más corto, teniendo en cuenta los pesos de nuestro gráfico ponderado. ¿Y si estuviéramos hablando de un gráfico aún más grande? De hecho, la mayoría de los gráficos con los que tratamos son mucho más grandes que veinte nodos. ¿Qué tan factible, escalable y eficiente sería para nosotros usar un enfoque de fuerza bruta para resolver este problema?

La respuesta es que no es tan factible. ¡Tampoco es realmente divertido! Y ahí es donde Dijkstra viene al rescate.

Reglas del juego de Dijkstra

El algoritmo de Dijkstra es único por muchas razones, que pronto veremos cuando empecemos a entender cómo funciona. Pero lo que siempre ha sido una pequeña sorpresa es el hecho de que este algoritmo no solo se usa para encontrar la ruta más corta entre dos nodos específicos en una estructura de datos de gráfico. El algoritmo de Dijkstra se puede utilizar para determinar la ruta más corta desde un nodo en un gráfico a cualquier otro nodo dentro de la misma estructura de datos del gráfico, siempre que se pueda acceder a los nodos desde el nodo inicial.

El algoritmo de Dijkstra se puede usar para encontrar el camino más corto.

Este algoritmo continuará ejecutándose hasta que se hayan visitado todos los vértices alcanzables en un gráfico, lo que significa que podríamos ejecutar el algoritmo de Dijkstra, encontrar la ruta más corta entre dos nodos accesibles y luego guardar los resultados en alguna parte. Una vez que ejecutamos el algoritmo de Dijkstra solo una vez, podemos buscar nuestros resultados de nuestro algoritmo una y otra vez, ¡sin tener que ejecutar el algoritmo en sí! La única vez que necesitaríamos volver a ejecutar el algoritmo de Dijkstra es si algo cambia sobre la estructura de datos de nuestro gráfico, en cuyo caso terminaríamos volviendo a ejecutar el algoritmo para asegurarnos de que todavía tengamos la información más actualizada. caminos más cortos para nuestra estructura de datos particular.

Entonces, ¿cómo funciona realmente el algoritmo de Dijkstra? ¡Es hora de descubrirlo finalmente!

Hay muchas rutas posibles entre el nodo A y el nodo E.

Considere el gráfico ponderado no dirigido de arriba. Digamos que queremos encontrar la ruta más corta del nodo a al nodo e. Sabemos que vamos a comenzar en el nodo a, ¡pero no sabemos si hay un camino para llegar a él o si hay muchos caminos para llegar a él! En cualquier caso, no sabemos qué ruta será la más corta para llegar al nodo e, si tal ruta existe.

El algoritmo de Dijkstra requiere un poco de configuración inicial. Pero, antes de llegar a eso, echemos un vistazo rápido a los pasos y las reglas para ejecutar el algoritmo de Dijkstra. En nuestro gráfico de ejemplo, comenzaremos con el nodo a como nuestro nodo inicial. Sin embargo, las reglas para ejecutar Dijkstra pueden resumirse para que puedan aplicarse a todos los nodos por los que atravesaremos y visitaremos en un esfuerzo por encontrar el camino más corto.

Pasos y reglas para ejecutar el algoritmo de Dijkstra.

Las reglas resumidas son las siguientes:

  1. Cada vez que nos proponemos visitar un nuevo nodo, elegiremos el nodo con la menor distancia / costo conocido para visitar primero.
  2. Una vez que nos hayamos trasladado al nodo que vamos a visitar, revisaremos cada uno de sus nodos vecinos.
  3. Para cada nodo vecino, calcularemos la distancia / costo para los nodos vecinos sumando el costo de los bordes que conducen al nodo que estamos verificando desde el vértice inicial.
  4. Finalmente, si la distancia / costo a un nodo es menor que una distancia conocida, actualizaremos la distancia más corta que tengamos en el archivo para ese vértice.

Estas instrucciones son nuestras reglas de oro que siempre seguiremos, hasta que nuestro algoritmo termine de ejecutarse. ¡Vamos a por ello!

Primero lo primero: necesitamos inicializar algunas cosas para realizar un seguimiento de cierta información importante a medida que se ejecuta este algoritmo.

Algoritmo de Dijkstra, parte 1

Crearemos una tabla para realizar un seguimiento de la distancia más corta conocida a cada vértice de nuestro gráfico. También realizaremos un seguimiento del vértice anterior del que venimos, antes de "verificar" el vértice que estamos viendo actualmente.

Una vez que tengamos nuestra tabla configurada, necesitaremos darle algunos valores. Cuando iniciamos el algoritmo de Dijkstra, ¡no sabemos nada en absoluto! Ni siquiera sabemos si todos los otros vértices que hemos enumerado (b, c, d, ye) son accesibles desde nuestro nodo inicial a.

Esto significa que, cuando comenzamos inicialmente, la "ruta más corta desde el nodo a" va a ser infinito (∞). Sin embargo, cuando comenzamos, conocemos la ruta más corta para un nodo y solo un nodo: por qué , nodo a, nuestro nodo inicial, por supuesto, ya que comenzamos en el nodo a, ya estamos allí para empezar. Entonces, la distancia más corta desde el nodo a al nodo a es en realidad solo 0.

Ahora que hemos inicializado nuestra tabla, necesitaremos otra cosa antes de poder ejecutar este algoritmo: ¡una forma de realizar un seguimiento de los nodos que hemos visitado o no! Podemos hacer esto simplemente con dos estructuras de matriz: una matriz visitada y una matriz no visitada.

Algoritmo de Dijkstra: configurar las cosas.

Cuando comenzamos, todavía no hemos visitado ningún nodo, por lo que todos nuestros nodos viven dentro de nuestra matriz no visitada.

Algoritmo de Dijkstra, parte 2

¡Bien, ahora estamos en buena forma! Empecemos. ¿Recuerdas nuestras cuatro reglas de antes? Vamos a seguirlos, paso a paso, a medida que trabajamos a través de cada vértice en este gráfico.

Primero, visitaremos el vértice con el costo / distancia más pequeño conocido. Podemos mirar la columna que nos dice la distancia más corta desde a. En este momento, cada vértice tiene una distancia de infinito (∞), ¡excepto un sí mismo! Entonces, visitaremos el nodo a.

A continuación, examinaremos sus nodos vecinos y calcularemos la distancia a ellos desde el vértice que estamos viendo actualmente (que es a). La distancia al nodo b es el costo de a más el costo para llegar al nodo b: en este caso, 7. De manera similar, la distancia al nodo c es el costo de a más el costo para llegar al nodo c: en este caso, 3)

Finalmente, si la distancia calculada es menor que nuestra distancia más corta actualmente conocida para estos nodos vecinos, actualizaremos los valores de nuestras tablas con nuestra nueva "distancia más corta". Bueno, actualmente, nuestra tabla dice que la distancia más corta de a a b es ∞, y lo mismo ocurre con la distancia más corta de a a c. Dado que 7 es menor que infinito, y 3 es menor que infinito, actualizaremos la distancia más corta del nodo b a 7, y la distancia más corta del nodo c a 3. También necesitaremos actualizar el vértice anterior de b y c, ya que necesitamos para mantener un registro de dónde venimos para obtener estos caminos! Actualizaremos el vértice anterior de byc a, ya que de ahí es de donde acabamos de llegar.

Ahora, hemos terminado de verificar los vecinos del nodo a, lo que significa que podemos marcarlo como visitado. En el siguiente nodo.

Algoritmo de Dijkstra, parte 3

Nuevamente, veremos el nodo con el menor costo que aún no se ha visitado. En este caso, el nodo c tiene un costo de 3, que es el costo más pequeño de todos los nodos no visitados. Entonces, el nodo c se convierte en nuestro vértice actual.

Repetiremos el mismo procedimiento que antes: verifique los vecinos no visitados del nodo c y calcule sus rutas más cortas desde nuestro nodo de origen, el nodo a. Los dos vecinos del nodo c que aún no han sido visitados son el nodo b y el nodo d. La distancia al nodo b es el costo de a más el costo de llegar del nodo c a b: en este caso, 4. La distancia al nodo d es el costo de a más el costo de llegar del nodo c a d: en este caso caso, 5.

Ahora, comparemos estas dos "distancias más cortas" con los valores que tenemos en nuestra tabla. En este momento, la distancia a d es infinita, por lo que ciertamente hemos encontrado una ruta de menor costo aquí, con un valor de 5. Pero, ¿qué pasa con la distancia al nodo b? Bueno, la distancia al nodo b está actualmente marcada como 7 en nuestra tabla. Pero, hemos encontrado una ruta más corta a b, que pasa por c, y tiene un costo de solo 4. ¡Así que actualizaremos nuestra tabla con nuestras rutas más cortas!

También tendremos que agregar el vértice c como el vértice anterior del nodo d. Observe que el nodo b ya tiene un vértice anterior, ya que encontramos una ruta antes, que ahora sabemos que en realidad no es la más corta. No se preocupe: simplemente tacharemos el vértice anterior para el nodo b y lo reemplazaremos por el vértice que, como ahora sabemos, tiene la ruta más corta: nodo c.

Algoritmo de Dijkstra, parte 4

Bien, ahora hemos visitado los nodos a y c. Entonces, ¿qué nodo visitamos a continuación?

Nuevamente, visitaremos el nodo que tiene el menor costo; en este caso, parece ser el nodo b, con un costo de 4.

Comprobaremos su vecino no visitado (solo tiene uno, nodo e), y calcularemos la distancia a e, desde el nodo de origen, a través de nuestro vértice actual, b.

Si sumamos el costo de b, que es 4, con el costo que se necesita para llegar de b a e, veremos que esto nos cuesta 6. Por lo tanto, terminamos con un costo total de 10 como el más corto. distancia conocida ae, desde el vértice inicial, a través de nuestro nodo actual.

Sin embargo, ¿cómo obtuvimos ese número?

Entonces, ¿cómo obtuvimos ese número? Al principio puede parecer confuso, pero podemos dividirlo en partes. Recuerde, no importa qué vértice estemos mirando, siempre queremos sumar la distancia más corta conocida desde nuestro inicio hasta nuestro vértice actual. En términos más simples, vamos a ver el valor de "distancia más corta" en nuestra tabla, que nos dará, en este ejemplo, el valor 4. Luego, veremos el costo desde nuestro vértice actual hasta el vecino que estamos examinando En este caso, el costo de b a e es 6, por lo que agregaremos eso a 4.

Por lo tanto, 6 + 4 = 10 es nuestra distancia más corta conocida al nodo e desde nuestro vértice inicial.

Detrás de escena de la magia de Dijkstra

Continuaremos haciendo los mismos pasos para cada vértice que permanezca sin visitar. El siguiente nodo que verificaríamos en este gráfico sería d, ya que tiene la distancia más corta de los nodos no visitados. Solo uno de los vecinos del nodo d no está visitado, que es el nodo e, por lo que es el único que tendremos que examinar.

Algoritmo de Dijkstra, parte 5

Cuando sumamos la distancia del nodo d y el costo para llegar del nodo d a e, veremos que terminamos con un valor de 9, que es menor que 10, la ruta más corta actual al nodo e. Actualizaremos nuestro valor de ruta más corto y el valor de vértice anterior para el nodo e en nuestra tabla.

Algoritmo de Dijkstra, parte 6

Finalmente, terminamos con solo un nodo para visitar: el nodo e.

Sin embargo, se hace bastante obvio que no hay nada que podamos hacer realmente aquí. No es necesario examinar ninguno de los vecinos del nodo e, ya que todos los vértices ya han sido visitados.

Todo lo que necesitamos hacer es marcar el nodo e como visitado. Ahora, ¡ya hemos terminado de ejecutar el algoritmo de Dijkstra en este gráfico!

Hemos tachado mucha información en el camino a medida que actualizamos y cambiamos los valores en nuestra tabla. Echemos un vistazo a una versión más bonita y limpia de esta tabla, con solo los resultados finales de este algoritmo.

Los valores finales del algoritmo de Dijkstra.

Al mirar esta tabla, puede que no sea completamente obvio, pero en realidad tenemos todos los caminos más cortos que se derivan de nuestro nodo inicial a disponible aquí, al alcance de la mano. Recordemos que antes, aprendimos que el algoritmo de Dijkstra puede ejecutarse una vez, y podemos reutilizar todos los valores una y otra vez, siempre que nuestro gráfico no cambie. Así es exactamente cómo esa característica se vuelve muy poderosa. Nos propusimos querer encontrar el camino más corto de a a e. ¡Pero esta tabla nos permitirá buscar todos los caminos más cortos!

Volviendo sobre nuestros pasos para encontrar el camino más corto.

La forma de buscar cualquier ruta más corta en esta tabla es volviendo sobre nuestros pasos y siguiendo el "vértice anterior" de cualquier nodo, de vuelta al nodo inicial.

Por ejemplo, supongamos que de repente decidimos que queremos encontrar el camino más corto de a a d. No es necesario volver a ejecutar el algoritmo de Dijkstra. ¡Ya tenemos toda la información que necesitamos, aquí mismo!

Usando una estructura de datos de pila, comenzaremos con el nodo d y lo empujaremos () a nuestra pila. Luego, veremos el vértice anterior del nodo d, que resulta ser el nodo b. Empujaremos () el nodo b a la pila. Del mismo modo, veremos el vértice anterior del nodo b (nodo c), y lo agregaremos a nuestra pila, y luego veremos el vértice anterior del nodo c, que es el nodo a, ¡nuestro vértice inicial!

Una vez que rastreamos nuestros pasos hasta nuestro vértice inicial, podemos sacar () cada vértice de la pila, lo que resulta en este orden: a - c - b - d. ¡Resulta que esta es la ruta exacta que nos dará el menor costo / distancia del nodo a al nodo d! Bastante rad, ¿verdad?

Se visualiza el algoritmo de Dijkstra, © Fundación Wikimedia

En muchos sentidos, el algoritmo de Dijkstra es una versión sofisticada de la forma típica de recorrido transversal de primer plano con el que ya estamos familiarizados. Las principales diferencias son el hecho de que es un poco más inteligente y puede manejar gráficos ponderados muy bien. Pero, si miramos el algoritmo de Dijkstra visualizado, como la animación que se muestra aquí, veremos que básicamente funciona como una búsqueda BFS, extendiéndose ampliamente en lugar de seguir profundamente una ruta específica.

El ejemplo más común del algoritmo de Dijkstra en la naturaleza es en problemas de búsqueda de ruta, como determinar direcciones o encontrar una ruta en GoogleMaps.

El algoritmo de Dijkstra implementado para encontrar rutas en un mapa.

Sin embargo, para encontrar un camino a través de GoogleMaps, una implementación del algoritmo de Dijkstra debe ser aún más inteligente que la que creamos hoy. La versión del algoritmo de Dijkstra que implementamos aquí todavía no es tan inteligente como la mayoría de las formas que se utilizan a nivel práctico. Imagine no solo un gráfico ponderado, sino también tener que calcular cosas como el tráfico, las condiciones de la carretera, los cierres de carreteras y la construcción.

Si todo esto parece mucho para asimilar, no se preocupe, ¡es algo complicado! De hecho, es un problema difícil que incluso Dijkstra tuvo problemas para ejemplificar bien. Resulta que cuando Edsger W. Dijkstra pensó por primera vez en el problema de encontrar el camino más corto en 1956, tuvo dificultades para tratar de encontrar un problema (y su solución) que fuera fácil de entender para las personas que lo hicieron. No viene del mundo de la informática! Finalmente se le ocurrió un buen problema de ejemplo para mostrar la importancia de poder encontrar el camino más corto. Él eligió, ¡lo has adivinado! - Un mapa como ejemplo. De hecho, cuando diseñó su algoritmo originalmente, lo implementó para una computadora llamada ARMAC. Utilizó el ejemplo de un mapa de transporte, que contenía ciudades de todos los Países Bajos, para mostrar cómo funcionaba su algoritmo.

Hacia el final de su vida, Dijkstra se sentó para una entrevista y reveló toda la historia de fondo cómo se le ocurrió su algoritmo ahora famoso:

¿Cuál es la forma más corta de viajar de Róterdam a Groninga? Es el algoritmo para el camino más corto que diseñé en unos 20 minutos. Una mañana estaba de compras con mi joven prometida, y cansado, nos sentamos en la terraza del café a tomar una taza de café y estaba pensando en si podría hacer esto, y luego diseñé el algoritmo para el camino más corto.

Entonces, ¿cuál es la moraleja de la historia? Estoy bastante seguro de que es tan simple como esto: no hay problema que no se pueda resolver con una buena taza de café.

Recursos

Para bien o para mal, el algoritmo de Dijkstra es uno de los métodos más conocidos de recorrido de gráficos en el mundo de la informática. La mala noticia es que a veces puede ser intimidante tratar de entender cómo funciona, ya que hay muchas referencias al respecto. La buena noticia es que hay muchos recursos disponibles, ¡solo necesita saber con cuáles comenzar! Aquí están algunos de mis favoritos.

  1. Estructura de datos gráficos: el algoritmo de ruta más corta de Dijkstra, Kevin Drumm
  2. Algoritmo de Dijkstra, Computerphile
  3. Algoritmo de rutas más cortas de Dijkstra para gráficos, Sesh Venugopal
  4. Un algoritmo de ruta más corta de fuente única para calcular la ruta más corta, la profesora Ileana Streinu
  5. Una nota sobre dos problemas en la conexión con gráficos, E.W. Dijkstra