Навигация в града с BFS и Dijkstra в JavaScript

Проблем

Куриерът пита за маршрут

Куриерската фирма от модула „Графи“ има склад в града. Картата е текстов файл, по една улица на ред: откъде, накъде и колко минути се кара по нея. - е двупосочна улица, -> е еднопосочна:

Склад - Гара 4
Склад - Пазар 3
Гара - Площад 3
Пазар - Площад 2
Пазар -> Парк 4
Площад - Кино 5
Кино - Болница 3
Парк - Стадион 2
Стадион - Болница 2
Склад - Стадион 16

Диспечерът иска маршрут от Склада до Болницата. Куриерът с велосипед пита за маршрута с най-малко кръстовища, защото на всяко спира. Куриерът с бус пита за най-бързия. Отговорите не са едни и същи.

Този проект е програмата, която чете картата и отговаря и на двата въпроса. Строиш я на стъпки, всяка с изход, с който да сравниш своя.

Идеята

Планът

Картата като граф. Кръстовищата са върхове, улиците са ребра с тегло: минутите. Както в „Граф: списък от съседи и матрица“, пазиш списък от съседи: речник от кръстовище към списък от улици.
Най-малко улици. BFS от Склада на слоеве: първо кръстовищата на една улица, после на две.
Минутите по маршрута. Сбор от минутите на улиците, за да сравниш двата отговора.
Най-бързо. Dijkstra с приоритетна опашка: винаги вади кръстовището с най-малко минути досега.
Обратно. Същата програма от Болницата към Склада. Еднопосочната улица прави пътя обратно различен.

Програмата чете картата от стандартния вход, за да работи с всяка карта. Пускаш я с файла: node main.mjs < map.txt.

Упражнение

Стъпка 1: картата

Прочети картата в речник от кръстовище към списък от улици (до кое кръстовище и колко минути). Двупосочната улица влиза в списъците и на двата края, еднопосочната само в списъка на началото. Кръстовище без изходящи улици също трябва да е в речника, с празен списък.

Отпечатай броя кръстовища и съседите на Склада, Пазара и Парка, в реда на редовете от файла:

кръстовища: 8
Склад: Гара 4, Пазар 3, Стадион 16
Пазар: Склад 3, Площад 2, Парк 4
Парк: Стадион 2

Решение

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(`кръстовища: ${city.size}`);
console.log(neighbors(city, "Склад"));
console.log(neighbors(city, "Пазар"));
console.log(neighbors(city, "Парк"));

Най-горе е import { readFileSync } from "node:fs";. readFileSync(0, "utf8") чете стандартния вход: файлов дескриптор 0. Файлът е .mjs, за да работи import.

Парк има един съсед, Стадиона: Пазар -> Парк е еднопосочна и Пазарът не е в списъка на Парка.

Упражнение

Стъпка 2: най-малко улици

Напиши fewestStreets(city, start, end): BFS от start, който спира, щом извади end, и връща маршрута като списък от кръстовища. За да построиш маршрута, пази за всяко кръстовище откъде си дошъл (prev), а после върви назад от end и обърни списъка.

най-малко улици: Склад → Стадион → Болница

Решение

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(`най-малко улици: ${fewestStreets(city, "Склад", "Болница").join(" → ")}`);

Кръстовището се маркира като видяно, когато влиза в опашката, не когато излиза: иначе едно кръстовище влиза няколко пъти.

Упражнение

Стъпка 3: колко минути

Добави minutesOf(city, route), който събира минутите на улиците по маршрута, и describe(city, route), който връща маршрута, броя улици и минутите. Отпечатай маршрута от стъпка 2 с describe:

най-малко улици: Склад → Стадион → Болница (2 улици, 18 мин)

Решение

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} улици, ${minutesOf(city, route)} мин)`;
}

const city = readMap(readFileSync(0, "utf8"));
console.log(`най-малко улици: ${describe(city, fewestStreets(city, "Склад", "Болница"))}`);

Две улици, но 18 минути: шестнайсет от тях са по околовръстното.

Виж го

Два маршрута на една карта

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 [];
}

Стъпка по стъпка, с думи

Картата: 8 кръстовища и 10 улици с минутите им. Пазар → Парк е еднопосочна, околовръстното от Склад до Стадион е 16 мин.
BFS, на една улица от Склад: Гара, Пазар, Стадион. Минутите не го интересуват.
На две улици: Площад, Парк, Болница. Болница вече е в опашката, от Стадион.
Най-малко улици: Склад → Стадион → Болница, 2 улици, но 18 мин: 16 от тях са по околовръстното.
Dijkstra: опашката е подредена по минути. Склад 0, съседите му влизат в опашката: Гара 4, Пазар 3, Стадион 16.
Най-бързото в опашката е Пазар, 3 мин. Ново: Площад 5, Парк 7.
Гара, 4 мин: през него нищо не става по-бързо.
Най-бързото в опашката е Площад, 5 мин. Ново: Кино 10.
Парк с 7 мин. През него Стадион пада от 16 на 9.
Най-бързото в опашката е Стадион, 9 мин. Ново: Болница 11.
Кино, 10 мин: през него нищо не става по-бързо.
Болница излиза с 11 мин: нищо в опашката не е по-бързо, значи това е отговорът.
Най-бързо: Склад → Пазар → Парк → Стадион → Болница, 4 улици, 11 мин.
Два отговора на два въпроса: 2 улици и 18 мин или 4 улици и 11 мин. За куриера важат минутите.

BFS вижда само броя улици и избира околовръстното. Dijkstra вади кръстовищата по минути и стига до Болницата за 11 мин през Пазара, еднопосочната улица и Стадиона. Стадионът първо е с 16 мин по шосето, после пада на 9 през Парка.

Упражнение

Стъпка 4: най-бързо

Напиши fastest(city, start, end) с Dijkstra: dist пази най-малките минути досега, опашката е подредена по минути, а prev пази маршрута. Отпечатай и двата маршрута:

най-малко улици: Склад → Стадион → Болница (2 улици, 18 мин)
най-бързо: Склад → Пазар → Парк → Стадион → Болница (4 улици, 11 мин)

Решение

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(`най-малко улици: ${describe(city, fewestStreets(city, "Склад", "Болница"))}`);
console.log(`най-бързо: ${describe(city, fastest(city, "Склад", "Болница"))}`);

JavaScript няма приоритетна опашка, затова е нужна своя: малък min-heap, като в урока за приоритетната опашка.

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;
  }
}

Пробвай

Попълни

Кръстовище може да влезе в опашката няколко пъти, когато минутите до него паднат. Старият запис остава. Какво прави програмата, когато го извади?

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

Пробвай

Предвиди пътя обратно

Куриерът се връща от Болницата към Склада. Програмата пита fastest(city, "Болница", "Склад"). Какво печата?

const city = readMap(readFileSync(0, "utf8"));
console.log(`обратно: ${describe(city, fastest(city, "Болница", "Склад"))}`);

Отговор

обратно: Болница → Кино → Площад → Пазар → Склад (4 улици, 13 мин)

обратно: Болница → Стадион → Склад (2 улици, 18 мин)

обратно: Болница → Стадион → Парк → Пазар → Склад (4 улици, 11 мин)

Упражнение

Стъпка 5: цялата програма

Добави пътя обратно. Цялата програма печата:

най-малко улици: Склад → Стадион → Болница (2 улици, 18 мин)
най-бързо: Склад → Пазар → Парк → Стадион → Болница (4 улици, 11 мин)
обратно: Болница → Кино → Площад → Пазар → Склад (4 улици, 13 мин)

Цялата програма

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} улици, ${minutesOf(city, route)} мин)`;
}

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(`най-малко улици: ${describe(city, fewestStreets(city, "Склад", "Болница"))}`);
console.log(`най-бързо: ${describe(city, fastest(city, "Склад", "Болница"))}`);
console.log(`обратно: ${describe(city, fastest(city, "Болница", "Склад"))}`);

Пробвай

Намери грешката

Колега е опростил addStreet. Сега пътят обратно излиза 11 мин:

обратно: Болница → Стадион → Парк → Пазар → Склад (4 улици, 11 мин)

Избери реда с грешката.

Виж го

Измери: градът расте

Истинският град има хиляди кръстовища. Решетката е проверка на скоростта: n кръстовища в квадрат, улиците са между съседите, с минути по формула. Куриерът тръгва от горния ляв ъгъл към долния десен:

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(`кръстовища: ${city.size}`);
const few = fewestStreets(city, "0:0", "99:99");
console.log(`най-малко улици: ${few.length - 1} улици, ${minutesOf(city, few)} мин`);
const fast = fastest(city, "0:0", "99:99");
console.log(`най-бързо: ${minutesOf(city, fast)} мин`);

кръстовища: 10000
най-малко улици: 198 улици, 990 мин
най-бързо: 693 мин

Пусни двата алгоритъма в браузъра. BFS гледа всяка улица веднъж: O(n). Dijkstra също, но всеки запис в heap-а струва O(log n): O(n log n). При n = 1000 това са 3966 срещу 15 778 операции, а при n = 100 000 са 398 158 срещу 2 348 779:

BFS: най-малко улици O(n)
Dijkstra: най-бързо O(n log n)

Алгоритъм	n = 10	n = 1000	n = 100 000
BFS: най-малко улици	22	3966	398 158
Dijkstra: най-бързо	34	15 778	2 348 779

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо 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 [];
}

По-точно, за любопитните

Dijkstra е по-бавен, но отговаря на въпроса за минутите, а BFS не може. И двата спират, щом извадят целта: за близка цел огледат малка част от града.

Навигациите за цели държави не пускат обикновен Dijkstra от всяко място. Те предварително обработват картата (например contraction hierarchies) и търсят с A*, който добавя оценка колко остава до целта. Основата пак е Dijkstra.

Упражнение

Ремонт на улицата

Реши задачата в редактора си.

Затворена улица. Улицата Парк – Стадион е затворена за ремонт. Добави към readMap множество от затворени улици ("Парк Стадион"), което пропуска тези редове в двете посоки. Отпечатай двата маршрута от Склада до Болницата:

най-малко улици: Склад → Стадион → Болница (2 улици, 18 мин)
най-бързо: Склад → Пазар → Площад → Кино → Болница (4 улици, 13 мин)

Още задачи

Само минутите. Напиши вариант на fastest, който връща минутите до всяко кръстовище, без да спира при целта. Кое кръстовище е най-далеч от Склада?
Без кръстовище. Площадът е затворен за събитие. Как ще го пропуснеш, без да пипаш картата?
Свободно шосе. През нощта околовръстното е празно и се кара за 6 мин. Смени минутите в картата: кой е най-бързият маршрут сега и съвпада ли с този на BFS?

Тест

Провери се

1. BFS и Dijkstra дават различни маршрути от Склада до Болницата. Кой е грешният?Dijkstra, защото минава повече улициНито един: BFS отговаря на „най-малко улици“, Dijkstra на „най-малко минути“BFS, защото е по-бавен

2. Защо BFS не намира най-бързия маршрут в този град?Улиците имат различни минути, а BFS брои всяка улица за еднаЗащото опашката е FIFOЗащото има еднопосочна улица

3. В Dijkstra записът, който излиза от опашката, понякога е с повече минути от dist. Какво прави програмата?Прескача го: кръстовището вече е извадено с по-малко минутиОбновява dist с по-голямото числоСпира

Когато минутите до кръстовище паднат, програмата слага нов запис, а старият остава в опашката. Когато старият излезе, той е остарял: minutes > dist[at], и се прескача.

4. Пазар -> Парк е еднопосочна. Какво трябва да има в списъка със съседи?Парк в съседите на Пазара, но не Пазар в съседите на ПаркаИ дветеСамо Пазар в съседите на Парка

5. Градът е решетка с n кръстовища. Как расте броят операции на двата алгоритъма?И двата O(n)И двата O(n²)BFS O(n), Dijkstra O(n log n): heap-ът добавя log n на улица

Навигация в града

Бисквитки