Cómo implementar el Algoritmo de Dijkstra en JavaScript

He estado leyendo Grokking Algorithms , que recomiendo a cualquier persona nueva en algoritmos. ¡Básicamente es la introducción que desearía haber tenido hace unos meses! Los ejemplos del libro están escritos en Python , por lo que me gustaría compartir una versión de JavaScript del algoritmo de Dijkstra . Este algoritmo utiliza un gráfico dirigido y ponderado para determinar la ruta "más barata" para llegar a un nodo.

Dividiré cada parte en unos pocos pasos, con información general. Si prefiere simplemente mirar el código, aquí está el enlace a la esencia.

Antecedentes: ¿Qué es un gráfico?

Un gráfico es un tipo de datos abstractos que se utiliza para modelar un conjunto de conexiones. Por ejemplo, digamos que Bob sigue a Sarah y Lou en Twitter. Sarah sigue a Lin. Lou sigue a Lin y Mark. Podemos representar estas conexiones usando un gráfico.

Cada persona es un nodo y cada conexión es un borde. Cada nodo se puede conectar a muchos otros nodos. Los gráficos se pueden dirigir para que cada conexión sea unidireccional, como en este ejemplo de Twitter: Bob sigue a Sarah, pero Sarah no sigue a Bob. Los gráficos también pueden no estar dirigidos para que las conexiones funcionen en ambos sentidos.

Los bordes de los gráficos también se pueden ponderar. Por ejemplo, en el gráfico a continuación, cada peso representa el costo que se necesita para ir de un punto a otro.

El reto

Supongamos que está tratando de averiguar la forma más económica de llegar a su destino, como se representa en el siguiente gráfico. Los nodos entre "inicio" y "finalización" son puentes y carreteras que puede tomar, y los pesos se refieren a los peajes/gasolina que tendrá que pagar.

Nuestro problema que estamos tratando de resolver.

A primera vista, ¡parece que las cosas podrían ponerse peludas! Hay muchas rutas posibles diferentes para evaluar y comparar. Y este gráfico es relativamente simple: ¿qué pasa si nos encontramos con un problema más complejo con más nodos y caminos posibles?

Pero el algoritmo de Dijkstra toma este problema intimidante y lo descompone, utilizando unos pocos pasos simples para llegar a la solución final. El algoritmo de Dijkstra también se ajusta bien a este caso de uso particular. El gráfico utilizado para representar los posibles caminos es dirigido y acíclico (lo que significa que no hay bucles).

El enfoque

Implementando el gráfico

Averigüemos cómo implementar el gráfico en nuestro programa. Usaré un objeto JavaScript anidado:

gráfico const = {inicio: {A: 5, B: 2},A: {C: 4, D: 2},B: {A: 8, D: 7},C: {D: 6, fin: 3 },D: {terminar: 1},terminar: {}};

Cada nodo está representado por las claves en el objeto gráfico. Cada clave tiene un objeto por su valor, que representa los vecinos inmediatos y el costo de llegar a ese vecino.

Por ejemplo, el nodo A está conectado a los nodos C y D. El nodo A es el "padre" de los nodos C y D, y son los "hijos" del nodo A.

Entendiendo el algoritmo

Ahora describamos los pasos principales en el algoritmo de Dijkstra.

1. Encuentre el nodo "más barato".
2. Actualice los costos de los vecinos inmediatos de este nodo.
3. Repita los pasos 1 y 2 hasta que haya hecho esto para cada nodo.
4. Devuelva el costo más bajo para llegar al nodo y la ruta óptima para hacerlo.

Entonces, si comenzamos en start , los primeros dos nodos que tenemos son A , que tiene un costo de 5 y B , que tiene un costo de 2. B es el nodo más barato. Estos son los únicos nodos que conocemos hasta ahora además de terminar. Y como aún no sabemos el costo por acabado , lo configuraremos en Infinito.

Eso ya es mucho de lo que hacer un seguimiento, ¡y solo hemos comenzado con el primer nodo! ¿Por qué no usamos una nueva estructura de datos para realizar un seguimiento del costo más bajo para llegar a cada nodo?

Usaremos un objeto para realizar un seguimiento de esto. Hasta ahora se ve algo como esto:

costos constantes = {A: 5, B: 2, terminar: Infinito};

Pero no solo queremos saber cuánto cuesta llegar al nodo final. ¡Queremos saber el camino que debemos tomar para llegar allí! Esto requiere el uso de otra estructura de datos para realizar un seguimiento del nodo principal de cada nodo. Cuando un nodo tiene muchos padres posibles, solo mantendremos el nodo padre que conduce al costo más bajo.

Así es como volvemos sobre el camino más barato que se necesita para llegar de principio a fin.

padres const = {A: 'inicio', B: 'inicio', finalizar: nulo};

En este momento, aún no conocemos la ruta completa para llegar al nodo de finalización , ya que no tenemos el padre de finalización.

Tampoco queremos perder el tiempo repasando los mismos nodos una y otra vez. Queremos rastrear qué nodos ya han sido "procesados". "Procesado" significa que ya hemos calculado el costo para llegar a cada uno de los hijos del nodo.

Para esto podemos simplemente usar una matriz. Una vez que se haya procesado un nodo, lo empujaremos a la matriz.

const procesado = [“inicio”, “A”, “B”];

Bien, aquí está el gráfico con el que estamos trabajando de nuevo.

Queremos seguir encontrando el nodo más barato y actualizando los costos de esos nodos hijos. El nodo más barato es B, y sus hijos son A (costo de 8) y D (costo de 7). Los agregamos a nuestro objeto de costos, que ahora se ve así:

console.log(costs)// devuelve algo como { A: 5,B: 2,D: 9finish: Infinity};

No actualizamos el costo de A , ya que 5 es más barato que 8. Agregamos D con un valor de 9, ya que el costo para llegar a B es 2, y el costo para llegar a D desde B es 7, entonces 7 + 2 = 9.

También actualizamos nuestras estructuras de datos primarios y procesados . Repetiremos los pasos anteriores hasta que hayamos procesado todos los nodos.

Implementando el algoritmo

Si esto aún no está claro, no se preocupe, estamos a punto de entrar en el código.

Primero definiremos una función que, dados los costos y los nodos procesados , devolverá el nodo más barato que no haya sido procesado.

const lowerCostNode = (costes, procesado) => {return Object.keys(costs).reduce((menor, nodo) => {if (menor === nulo || costes[nodo] <costes[menor]) {if (!procesado.incluye(nodo)) {menor = nodo;}}devuelve el menor;}, nulo);};

Luego definiremos la función principal, dijkstra , que tomará el gráfico inicial como parámetro. Comenzaremos creando las estructuras de costos , padres y datos procesados .

const dijkstra = (gráfico) => {

costos constantes = Object.assign({finish: Infinity}, graph.start);

const padres = {terminar: nulo};

for (let child in graph.start) { // agregar hijos de start nodeparents[child] = 'start';}

const procesado = [];

...

A continuación, estableceremos el valor inicial del nodo que se está procesando mediante la función lowerCostNode . Luego, comenzaremos un ciclo while , que buscará continuamente el nodo más barato.

let node = lowerCostNode(costos, procesado);while (nodo) {

 let cost = costs\[node\]; let children = graph\[node\]; for (let n in children) { let newCost = cost + children\[n\]; if (!costs\[n\]) { costs\[n\] = newCost; parents\[n\] = node; } if (costs\[n\] > newCost) { costs\[n\] = newCost; parents\[n\] = node; } } processed.push(node); node = lowestCostNode(costs, processed);

}

Aquí hay una descripción de lo que está sucediendo arriba con mayor detalle:

1. Obtenga el costo del nodo actual
2. Obtenga todos los vecinos (también conocidos como "hijos") del nodo actual.
3. Recorra cada uno de los elementos secundarios y calcule el costo para llegar a ese nodo secundario. Actualizaremos el costo de ese nodo en el objeto de costos si es el más barato o el único costo disponible.
4. También actualizaremos la estructura de datos de los padres, para que podamos volver sobre nuestros pasos al final.
5. Una vez que el nodo esté completamente procesado, lo enviaremos a nuestra estructura de datos procesados.
6. Restablezca el valor del nodo actual al nodo más barato sin procesar y repita.

Finalmente, una vez que se complete el ciclo while, tendremos el costo más bajo para llegar al nodo final . Ahora queremos obtener la ruta a ese nodo, lo que podemos hacer volviendo sobre nuestros pasos con el objeto principal.

let rutaoptima = ['terminar'];

let padre = padres.terminar;

while (padre) {optimalPath.push(padre);padre = padres[padre];}

rutaoptima.reverse(); // matriz inversa para obtener el orden correcto

const resultados = {distancia: costos.terminar,ruta: rutaoptima};

devolver resultados;

}; //fin de la función

¡Nuestro resultado final debería verse así!

{ distancia: 8, ruta: [ 'inicio', 'A', 'D', 'terminar'] }

Para ver la solución completa, echa un vistazo a la esencia.

Si aún tiene problemas, le recomiendo ejecutar el código en su máquina y cambiar partes del programa. Descubrí que ajustar y jugar con el código realmente me ayuda a obtener una comprensión más profunda de lo que está sucediendo.

Espero que hayas disfrutado esta explicación. ¡Gracias por tomarse el tiempo de leer este artículo!

** ACTUALIZACIÓN: para mayor claridad, revisé mi solución original e incorporé comentarios y nombres de variables más claros, junto con algunos registros para ayudar a comprender lo que está sucediendo. Puedes encontrarlo aquí .

— — Si disfrutó de esta pieza, presione el corazón verde 💚 para que otros también puedan tropezar con ella. Siéntete libre de seguirme en Github o Twitter también.