Navegación por la ciudad con BFS y Dijkstra en JavaScript

Problema

El mensajero pide una ruta

La empresa de mensajería del módulo «Grafos» tiene un almacén en la ciudad. El mapa es un archivo de texto con una calle por línea: desde dónde, hasta dónde y cuántos minutos se tarda en recorrerla. - es una calle de doble sentido, -> una de sentido único:

Almacén - Estación 4
Almacén - Mercado 3
Estación - Plaza 3
Mercado - Plaza 2
Mercado -> Parque 4
Plaza - Cine 5
Cine - Hospital 3
Parque - Estadio 2
Estadio - Hospital 2
Almacén - Estadio 16

El despachador necesita una ruta del almacén al hospital. El mensajero en bicicleta pide la ruta con menos cruces, porque se detiene en cada uno. El mensajero de la furgoneta pide la más rápida. Las respuestas no son las mismas.

Este proyecto es el programa que lee el mapa y responde a las dos preguntas. Lo construyes por pasos, cada uno con una salida con la que comparar la tuya.

La idea

El plan

El mapa como grafo. Los cruces son vértices, las calles son aristas con peso: los minutos. Como en «Grafo: lista de adyacencia y matriz», guardas una lista de adyacencia: un diccionario de un cruce a una lista de calles.
Menos calles. BFS desde el almacén por capas: primero los cruces a una calle, luego a dos.
Los minutos de una ruta. La suma de los minutos de sus calles, para comparar las dos respuestas.
Lo más rápido. Dijkstra con una cola de prioridad: siempre saca el cruce con menos minutos hasta ahora.
La vuelta. El mismo programa del hospital al almacén. La calle de sentido único hace distinto el camino de vuelta.

El programa lee el mapa de la entrada estándar, para funcionar con cualquier mapa. Lo ejecutas con el archivo: node main.mjs < map.txt.

Ejercicio

Paso 1: el mapa

Lee el mapa en un diccionario de un cruce a una lista de calles (a qué cruce y cuántos minutos). Una calle de doble sentido va a las listas de los dos extremos, una de sentido único solo a la lista de su inicio. Un cruce sin calles de salida también debe estar en el diccionario, con una lista vacía.

Imprime el número de cruces y los vecinos del Almacén, el Mercado y el Parque, en el orden de las líneas del archivo:

cruces: 8
Almacén: Estación 4, Mercado 3, Estadio 16
Mercado: Almacén 3, Plaza 2, Parque 4
Parque: Estadio 2

Solución

function addStreet(city, a, b, minutes, twoWay) {
  if (!city.has(a)) city.set(a, []);
  if (!city.has(b)) city.set(b, []);
  city.get(a).push({ to: b, minutes });
  if (twoWay) city.get(b).push({ to: a, minutes });
}

function readMap(text) {
  const city = new Map();
  for (const line of text.trim().split("\n")) {
    const [a, kind, b, minutes] = line.trim().split(/\s+/);
    addStreet(city, a, b, Number(minutes), kind === "-");
  }
  return city;
}

function neighbors(city, place) {
  return `${place}: ${city.get(place).map((s) => `${s.to} ${s.minutes}`).join(", ")}`;
}

const city = readMap(readFileSync(0, "utf8"));
console.log(`cruces: ${city.size}`);
console.log(neighbors(city, "Almacén"));
console.log(neighbors(city, "Mercado"));
console.log(neighbors(city, "Parque"));

Arriba del todo está import { readFileSync } from "node:fs";. readFileSync(0, "utf8") lee la entrada estándar: el descriptor de archivo 0. El archivo es .mjs para que funcione import.

El Parque tiene un vecino, el Estadio: Mercado -> Parque es de sentido único y el Mercado no está en la lista del Parque.

Ejercicio

Paso 2: menos calles

Escribe fewestStreets(city, start, end): un BFS desde start que se detiene en cuanto saca end y devuelve la ruta como lista de cruces. Para construir la ruta, guarda para cada cruce de dónde viniste (prev), luego retrocede desde end y da la vuelta a la lista.

menos calles: Almacén → Estadio → Hospital

Solución

function route(prev, end) {
  const places = [];
  for (let at = end; at !== undefined; at = prev.get(at)) places.push(at);
  return places.reverse();
}

function fewestStreets(city, start, end) {
  const prev = new Map();
  const seen = new Set([start]);
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const at = queue[head];
    if (at === end) return route(prev, end);
    for (const { to } of city.get(at)) {
      if (!seen.has(to)) {
        seen.add(to);
        prev.set(to, at);
        queue.push(to);
      }
    }
  }
  return [];
}

const city = readMap(readFileSync(0, "utf8"));
console.log(`menos calles: ${fewestStreets(city, "Almacén", "Hospital").join(" → ")}`);

Un cruce se marca como visto cuando entra en la cola, no cuando sale: si no, un mismo cruce entra varias veces.

Ejercicio

Paso 3: cuántos minutos

Añade minutesOf(city, route), que suma los minutos de las calles a lo largo de la ruta, y describe(city, route), que devuelve la ruta, el número de calles y los minutos. Imprime la ruta del paso 2 con describe:

menos calles: Almacén → Estadio → Hospital (2 calles, 18 min)

Solución

function minutesOf(city, route) {
  let total = 0;
  for (let i = 1; i < route.length; i++) {
    total += city.get(route[i - 1]).find((s) => s.to === route[i]).minutes;
  }
  return total;
}

function describe(city, route) {
  return `${route.join(" → ")} (${route.length - 1} calles, ${minutesOf(city, route)} min)`;
}

const city = readMap(readFileSync(0, "utf8"));
console.log(`menos calles: ${describe(city, fewestStreets(city, "Almacén", "Hospital"))}`);

Dos calles, pero 18 minutos: dieciséis de ellos en la circunvalación.

Míralo

Dos rutas en un mapa

function fastest(city, start, end) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = new MinHeap();
  queue.push(0, start);
  while (queue.size > 0) {
    const [minutes, at] = queue.pop();
    if (minutes > dist.get(at)) continue;
    if (at === end) return route(prev, end);
    for (const { to, minutes: length } of city.get(at)) {
      const t = minutes + length;
      if (!dist.has(to) || t < dist.get(to)) {
        dist.set(to, t);
        prev.set(to, at);
        queue.push(t, to);
      }
    }
  }
  return [];
}

function fewestStreets(city, start, end) {
  const prev = new Map();
  const seen = new Set([start]);
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const at = queue[head];
    if (at === end) return route(prev, end);
    for (const { to } of city.get(at)) {
      if (!seen.has(to)) {
        seen.add(to);
        prev.set(to, at);
        queue.push(to);
      }
    }
  }
  return [];
}

Paso a paso, en palabras

El mapa: 8 cruces y 10 calles con sus minutos. Mercado → Parque es de sentido único, la circunvalación de Almacén a Estadio son 16 min.
BFS, a una calle de Almacén: Estación, Mercado, Estadio. A él no le importan los minutos.
A dos calles: Plaza, Parque, Hospital. Hospital ya está en la cola, desde Estadio.
Menos calles: Almacén → Estadio → Hospital, 2 calles, pero 18 min: 16 de ellos son de la circunvalación.
Dijkstra: la cola está ordenada por minutos. Almacén 0, sus vecinos entran en la cola: Estación 4, Mercado 3, Estadio 16.
Lo más rápido en la cola es Mercado, 3 min. Nuevo: Plaza 5, Parque 7.
Estación, 4 min: por él nada se vuelve más rápido.
Lo más rápido en la cola es Plaza, 5 min. Nuevo: Cine 10.
Parque con 7 min. Por él Estadio baja de 16 a 9.
Lo más rápido en la cola es Estadio, 9 min. Nuevo: Hospital 11.
Cine, 10 min: por él nada se vuelve más rápido.
Hospital sale con 11 min: nada en la cola es más rápido, así que esta es la respuesta.
Más rápido: Almacén → Mercado → Parque → Estadio → Hospital, 4 calles, 11 min.
Dos respuestas a dos preguntas: 2 calles y 18 min o 4 calles y 11 min. Para el mensajero cuentan los minutos.

BFS solo ve el número de calles y elige la circunvalación. Dijkstra saca los cruces por minutos y llega al hospital en 11 min por el Mercado, la calle de sentido único y el Estadio. El Estadio primero tiene 16 min por la circunvalación, luego baja a 9 por el Parque.

Ejercicio

Paso 4: lo más rápido

Escribe fastest(city, start, end) con Dijkstra: dist guarda los minutos mínimos hasta ahora, la cola está ordenada por minutos y prev guarda la ruta. Imprime las dos rutas:

menos calles: Almacén → Estadio → Hospital (2 calles, 18 min)
más rápido: Almacén → Mercado → Parque → Estadio → Hospital (4 calles, 11 min)

Solución

function fastest(city, start, end) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = new MinHeap();
  queue.push(0, start);
  while (queue.size > 0) {
    const [minutes, at] = queue.pop();
    if (minutes > dist.get(at)) continue;
    if (at === end) return route(prev, end);
    for (const { to, minutes: length } of city.get(at)) {
      const t = minutes + length;
      if (!dist.has(to) || t < dist.get(to)) {
        dist.set(to, t);
        prev.set(to, at);
        queue.push(t, to);
      }
    }
  }
  return [];
}

const city = readMap(readFileSync(0, "utf8"));
console.log(`menos calles: ${describe(city, fewestStreets(city, "Almacén", "Hospital"))}`);
console.log(`más rápido: ${describe(city, fastest(city, "Almacén", "Hospital"))}`);

JavaScript no tiene cola de prioridad, así que necesitas la tuya: un pequeño min-heap, como en la lección sobre la cola de prioridad.

class MinHeap {
  constructor() {
    this.items = [];
  }

  get size() {
    return this.items.length;
  }

  push(priority, value) {
    const a = this.items;
    a.push([priority, value]);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }

  pop() {
    const a = this.items;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1;
        const r = l + 1;
        let m = i;
        if (l < a.length && a[l][0] < a[m][0]) m = l;
        if (r < a.length && a[r][0] < a[m][0]) m = r;
        if (m === i) break;
        [a[m], a[i]] = [a[i], a[m]];
        i = m;
      }
    }
    return top;
  }
}

Pruébalo

Completa

Un cruce puede entrar en la cola varias veces, cuando bajan los minutos hasta él. La entrada vieja se queda. ¿Qué hace el programa cuando la saca?

if (minutes > dist.get(at)) ;

Pruébalo

Predice la vuelta

El mensajero vuelve del hospital al almacén. El programa pregunta fastest(city, "Hospital", "Almacén"). ¿Qué imprime?

const city = readMap(readFileSync(0, "utf8"));
console.log(`vuelta: ${describe(city, fastest(city, "Hospital", "Almacén"))}`);

Respuesta

vuelta: Hospital → Estadio → Parque → Mercado → Almacén (4 calles, 11 min)

vuelta: Hospital → Estadio → Almacén (2 calles, 18 min)

vuelta: Hospital → Cine → Plaza → Mercado → Almacén (4 calles, 13 min)

Ejercicio

Paso 5: el programa completo

Añade la vuelta. El programa completo imprime:

menos calles: Almacén → Estadio → Hospital (2 calles, 18 min)
más rápido: Almacén → Mercado → Parque → Estadio → Hospital (4 calles, 11 min)
vuelta: Hospital → Cine → Plaza → Mercado → Almacén (4 calles, 13 min)

El programa completo

import { readFileSync } from "node:fs";

class MinHeap {
  constructor() {
    this.items = [];
  }

  get size() {
    return this.items.length;
  }

  push(priority, value) {
    const a = this.items;
    a.push([priority, value]);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }

  pop() {
    const a = this.items;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1;
        const r = l + 1;
        let m = i;
        if (l < a.length && a[l][0] < a[m][0]) m = l;
        if (r < a.length && a[r][0] < a[m][0]) m = r;
        if (m === i) break;
        [a[m], a[i]] = [a[i], a[m]];
        i = m;
      }
    }
    return top;
  }
}

function addStreet(city, a, b, minutes, twoWay) {
  if (!city.has(a)) city.set(a, []);
  if (!city.has(b)) city.set(b, []);
  city.get(a).push({ to: b, minutes });
  if (twoWay) city.get(b).push({ to: a, minutes });
}

function readMap(text) {
  const city = new Map();
  for (const line of text.trim().split("\n")) {
    const [a, kind, b, minutes] = line.trim().split(/\s+/);
    addStreet(city, a, b, Number(minutes), kind === "-");
  }
  return city;
}

function route(prev, end) {
  const places = [];
  for (let at = end; at !== undefined; at = prev.get(at)) places.push(at);
  return places.reverse();
}

function fewestStreets(city, start, end) {
  const prev = new Map();
  const seen = new Set([start]);
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const at = queue[head];
    if (at === end) return route(prev, end);
    for (const { to } of city.get(at)) {
      if (!seen.has(to)) {
        seen.add(to);
        prev.set(to, at);
        queue.push(to);
      }
    }
  }
  return [];
}

function minutesOf(city, route) {
  let total = 0;
  for (let i = 1; i < route.length; i++) {
    total += city.get(route[i - 1]).find((s) => s.to === route[i]).minutes;
  }
  return total;
}

function describe(city, route) {
  return `${route.join(" → ")} (${route.length - 1} calles, ${minutesOf(city, route)} min)`;
}

function fastest(city, start, end) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = new MinHeap();
  queue.push(0, start);
  while (queue.size > 0) {
    const [minutes, at] = queue.pop();
    if (minutes > dist.get(at)) continue;
    if (at === end) return route(prev, end);
    for (const { to, minutes: length } of city.get(at)) {
      const t = minutes + length;
      if (!dist.has(to) || t < dist.get(to)) {
        dist.set(to, t);
        prev.set(to, at);
        queue.push(t, to);
      }
    }
  }
  return [];
}

const city = readMap(readFileSync(0, "utf8"));
console.log(`menos calles: ${describe(city, fewestStreets(city, "Almacén", "Hospital"))}`);
console.log(`más rápido: ${describe(city, fastest(city, "Almacén", "Hospital"))}`);
console.log(`vuelta: ${describe(city, fastest(city, "Hospital", "Almacén"))}`);

Pruébalo

Encuentra el error

Un compañero ha acortado addStreet. Ahora la vuelta sale en 11 min:

vuelta: Hospital → Estadio → Parque → Mercado → Almacén (4 calles, 11 min)

Elige la línea con el error.

Míralo

Mide: la ciudad crece

Una ciudad real tiene miles de cruces. La cuadrícula es una prueba de velocidad: n cruces en un cuadrado, calles entre vecinos, minutos según una fórmula. El mensajero sale de la esquina superior izquierda y va a la inferior derecha:

function gridCity(size) {
  const city = new Map();
  for (let r = 0; r < size; r++) {
    for (let c = 0; c < size; c++) {
      const at = `${r}:${c}`;
      if (c + 1 < size) addStreet(city, at, `${r}:${c + 1}`, 1 + ((r * 7 + c * 13) % 9), true);
      if (r + 1 < size) addStreet(city, at, `${r + 1}:${c}`, 1 + ((r * 11 + c * 5) % 9), true);
    }
  }
  return city;
}

const city = gridCity(100);
console.log(`cruces: ${city.size}`);
const few = fewestStreets(city, "0:0", "99:99");
console.log(`menos calles: ${few.length - 1} calles, ${minutesOf(city, few)} min`);
const fast = fastest(city, "0:0", "99:99");
console.log(`más rápido: ${minutesOf(city, fast)} min`);

cruces: 10000
menos calles: 198 calles, 990 min
más rápido: 693 min

Ejecuta los dos algoritmos en el navegador. BFS mira cada calle una vez: O(n). Dijkstra también, pero cada entrada del heap cuesta O(log n): O(n log n). Con n = 1000 son 3966 frente a 15.778 operaciones, y con n = 100 000 son 398.158 frente a 2.348.779:

BFS: la menor cantidad de calles O(n)
Dijkstra: el más rápido O(n log n)

Algoritmo	n = 10	n = 1000	n = 100.000
BFS: la menor cantidad de calles	22	3966	398.158
Dijkstra: el más rápido	34	15.778	2.348.779

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

function fastest(city, start, end) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = new MinHeap();
  queue.push(0, start);
  while (queue.size > 0) {
    const [minutes, at] = queue.pop();
    if (minutes > dist.get(at)) continue;
    if (at === end) return route(prev, end);
    for (const { to, minutes: length } of city.get(at)) {
      const t = minutes + length;
      if (!dist.has(to) || t < dist.get(to)) {
        dist.set(to, t);
        prev.set(to, at);
        queue.push(t, to);
      }
    }
  }
  return [];
}

Más precisamente, para curiosos

Dijkstra es más lento, pero responde a la pregunta de los minutos, y BFS no puede. Los dos se detienen en cuanto sacan el destino: para un destino cercano miran una parte pequeña de la ciudad.

La navegación de países enteros no ejecuta un Dijkstra simple desde cada lugar. Preprocesa el mapa (por ejemplo con contraction hierarchies) y busca con A*, que añade una estimación de cuánto falta hasta el destino. La base sigue siendo Dijkstra.

Ejercicio

Obras en la calle

Resuelve esta en tu editor.

Una calle cerrada. La calle Parque – Estadio está cerrada por obras. Dale a readMap un conjunto de calles cerradas ("Parque Estadio") que salte esas líneas en los dos sentidos. Imprime las dos rutas del almacén al hospital:

menos calles: Almacén → Estadio → Hospital (2 calles, 18 min)
más rápido: Almacén → Mercado → Plaza → Cine → Hospital (4 calles, 13 min)

Más tareas

Solo los minutos. Escribe una variante de fastest que devuelva los minutos hasta cada cruce sin detenerse en el destino. ¿Qué cruce es el más lejano del almacén?
Sin un cruce. La Plaza está cerrada por un evento. ¿Cómo la dejas fuera sin tocar el mapa?
Una circunvalación vacía. De noche la circunvalación está vacía y se recorre en 6 min. Cambia los minutos en el mapa: ¿cuál es ahora la ruta más rápida y es la misma que la de BFS?

Test

Ponte a prueba

1. BFS y Dijkstra dan rutas distintas del almacén al hospital. ¿Cuál está mal?BFS, porque es más lentoNinguna: BFS responde a «menos calles», Dijkstra a «menos minutos»Dijkstra, porque pasa por más calles

2. ¿Por qué BFS no encuentra la ruta más rápida en esta ciudad?Porque la cola es FIFOLas calles tardan minutos distintos, y BFS cuenta cada calle como unaPorque hay una calle de sentido único

3. En Dijkstra, la entrada que sale de la cola a veces tiene más minutos que dist. ¿Qué hace el programa?Actualiza dist con el número mayorSe detieneLa salta: el cruce ya salió con menos minutos

Cuando bajan los minutos hasta un cruce, el programa añade una entrada nueva y la vieja se queda en la cola. Cuando la vieja sale, está caducada: minutes > dist[at], y se salta.

4. Mercado -> Parque es de sentido único. ¿Qué debe haber en la lista de adyacencia?Parque entre los vecinos del Mercado, pero no Mercado entre los vecinos del ParqueLas dos cosasSolo Mercado entre los vecinos del Parque

5. La ciudad es una cuadrícula con n cruces. ¿Cómo crece el número de operaciones de los dos algoritmos?Los dos O(n)Los dos O(n²)BFS O(n), Dijkstra O(n log n): el heap añade log n por calle

Navegación por la ciudad

Cookies