Към съдържанието
wannacode

Dijkstra

Накратко: Алгоритъмът на Dijkstra намира най-кратките пътища от един връх в граф с неотрицателни тегла, като взима най-близкия връх от приоритетна опашка: O((V + E) log V).

Проблем

Най-малко улици не е най-бързо

Куриерът тръгва от склада към клиент. Приложението трябва да му даде най-бързия маршрут. Всяка улица има време в минути: булевардът е широк, но в задръстване, а малките улички са бързи.

Градът е граф, улиците са ребрата му в двете посоки (виж представянето на граф):

function addStreet(city, a, b, minutes) {
  if (!city.has(a)) city.set(a, []);
  if (!city.has(b)) city.set(b, []);
  city.get(a).push({ to: b, minutes });
  city.get(b).push({ to: a, minutes });
}
const city = new Map();
addStreet(city, "Склад", "Мост", 2);
addStreet(city, "Склад", "Площад", 5);
addStreet(city, "Склад", "Пазар", 15);
addStreet(city, "Мост", "Площад", 1);
addStreet(city, "Мост", "Гара", 8);
addStreet(city, "Площад", "Гара", 3);
addStreet(city, "Площад", "Пазар", 9);
addStreet(city, "Гара", "Клиент", 3);
addStreet(city, "Пазар", "Клиент", 2);

Първата идея е BFS от предишния урок: той намира най-късия път. Но BFS брои улиците, не минутите:

function fewestStreets(city, start) {
  const prev = new Map();
  const seen = new Set([start]);
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    for (const { to } of city.get(queue[head])) {
      if (seen.has(to)) continue;
      seen.add(to);
      prev.set(to, queue[head]);
      queue.push(to);
    }
  }
  return prev;
}
const city = new Map();
addStreet(city, "Склад", "Мост", 2);
addStreet(city, "Склад", "Площад", 5);
addStreet(city, "Склад", "Пазар", 15);
addStreet(city, "Мост", "Площад", 1);
addStreet(city, "Мост", "Гара", 8);
addStreet(city, "Площад", "Гара", 3);
addStreet(city, "Площад", "Пазар", 9);
addStreet(city, "Гара", "Клиент", 3);
addStreet(city, "Пазар", "Клиент", 2);
const r = route(fewestStreets(city, "Склад"), "Клиент");
console.log(`Най-малко улици: ${r.join(" → ")} (${r.length - 1} улици, ${minutes(city, r)} мин)`);
Изход
Най-малко улици: Склад → Пазар → Клиент (2 улици, 17 мин)

Две улици, но 17 минути: 15 по булеварда до пазара и 2 до клиента. През моста, площада и гарата са четири улици и само 9 минути. BFS дори не гледа минутите.

Идеята

Най-близкото място първо

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

Това прави алгоритъмът на Dijkstra (Едсхер Дейкстра, 1956). Пази за всяко място най-доброто време досега, dist, и опашка от записи „минути, място“.

  1. Отначало dist е 0 за склада, а всяко друго място е недостигнато (∞).
  2. Вземи от опашката записа с най-малко минути. Това е приоритетна опашка: вади най-малкото за O(log n).
  3. За всяка улица от това място пробвай: стига ли се по нея до съседа по-бързо от досегашното? Ако да, запиши новото време, запомни откъде си дошъл (prev) и сложи нов запис в опашката. Това пробване се казва релаксация (relaxation).
  4. Повтаряй, докато опашката свърши.

Защо мястото, което излиза от опашката, вече има окончателното си време? Всички други записи са с поне толкова минути, а всяка улица добавя минути. Никой път през тях не може да стигне по-рано.

Виж го

Dijkstra отвътре

function dijkstra(city, start) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = new MinQueue();
  queue.push({ place: start, minutes: 0 });
  while (queue.size > 0) {
    const { place, minutes } = queue.poll();
    if (minutes > dist.get(place)) continue; // остаряло
    for (const street of city.get(place)) {
      const t = minutes + street.minutes;
      const to = street.to;
      if (!dist.has(to) || t < dist.get(to)) {
        dist.set(to, t);
        prev.set(to, place);
        queue.push({ place: to, minutes: t });
      }
    }
  }
  return { dist, prev };
}
JavaScript няма вградена приоритетна опашка, затова MinQueue е DeadlineQueue от урока за приоритетната опашка, която сравнява minutes вместо deadline. Място, което го няма в dist, още не е достигнато: това е ∞.

prev пази маршрута отзад напред: за всяко място, откъде е дошъл най-бързият път. Тръгваш от клиента, следваш prev до склада и обръщаш:

function route(prev, end) {
  const places = [];
  for (let at = end; at !== undefined; at = prev.get(at)) places.push(at);
  return places.reverse();
}
const { dist, prev } = dijkstra(city, "Склад");
const r = route(prev, "Клиент");
console.log(`Най-бързо: ${r.join(" → ")} (${r.length - 1} улици, ${minutes(city, r)} мин)`);
Изход
Най-бързо: Склад → Мост → Площад → Гара → Клиент (4 улици, 9 мин)

function dijkstra(city, start) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = new MinQueue();
  queue.push({ place: start, minutes: 0 });
  while (queue.size > 0) {
    const { place, minutes } = queue.poll();
    if (minutes > dist.get(place)) continue; // остаряло
    for (const street of city.get(place)) {
      const t = minutes + street.minutes;
      const to = street.to;
      if (!dist.has(to) || t < dist.get(to)) {
        dist.set(to, t);
        prev.set(to, place);
        queue.push({ place: to, minutes: t });
      }
    }
  }
  return { dist, prev };
}
Стъпка по стъпка, с думи
  1. Куриерът тръгва от Склад: 0 минути. Всяко друго място е ∞, още нищо не го е стигнало. В опашката има един запис: 0 Склад.
  2. Взима се най-малкият запис, 0 Склад. Всяка улица от него дава време: Мост 2, Площад 5, Пазар 15. Всички са по-добри от ∞: записват се и влизат в опашката.
  3. Следва 2 Мост. През него Площад е 2 + 1 = 3, по-добро от 5: времето и prev се сменят, влиза 3 Площад. Старото 5 Площад остава в опашката, вече е остаряло. Гара получава 10.
  4. 3 Площад: окончателно, нищо в опашката не може да го направи по-бързо. През него Гара пада от 10 на 6, а Пазар от 15 на 12.
  5. Отгоре е 5 Площад, но Площад вече има 3. Записът е остарял: прескача се. Това е мързеливото изтриване: вместо да търсиш стария запис в опашката, го изхвърляш, когато излезе.
  6. 6 Гара: окончателно. Клиент получава 6 + 3 = 9. Обратно към Мост с 14 и Площад с 9 не е по-добре.
  7. 9 Клиент: окончателно, 9 минути. През Клиент Пазар пада от 12 на 11. Границата расте по време, а не по брой улици.
  8. Останалото: 10 Гара е остаряло, 11 Пазар е окончателно и не подобрява нищо, 12 и 15 Пазар са остарели. Опашката е празна.
  9. prev дава маршрута отзад напред: Клиент ← Гара ← Площад ← Мост ← Склад. Обърнат: Склад → Мост → Площад → Гара → Клиент, 9 минути, четири улици. Маршрутът с две улици през Пазар е 17.

Местата стават окончателни по реда на времето си: Склад 0, Мост 2, Площад 3, Гара 6, Клиент 9, Пазар 11. Пазарът, който е на една улица от склада, е последен.

Пробвай

Предвиди изхода

Колко минути до пазара дава Dijkstra?

const city = new Map();
addStreet(city, "Склад", "Мост", 2);
addStreet(city, "Склад", "Площад", 5);
addStreet(city, "Склад", "Пазар", 15);
addStreet(city, "Мост", "Площад", 1);
addStreet(city, "Мост", "Гара", 8);
addStreet(city, "Площад", "Гара", 3);
addStreet(city, "Площад", "Пазар", 9);
addStreet(city, "Гара", "Клиент", 3);
addStreet(city, "Пазар", "Клиент", 2);
console.log(dijkstra(city, "Склад").dist.get("Пазар"));
Отговор

Идеята

Остарелите записи

Когато площадът получи 3 минути вместо 5, записът „5 Площад“ вече е в опашката. Защо не го сменим на място?

Вградените опашки не могат: нашата MinQueue няма „смени приоритета“, както и пакетите от npm обикновено. Затова по-доброто време влиза като нов запис. Старият остава, а когато излезе, проверката го хвърля: времето му е по-голямо от записаното в dist. Това е мързеливо изтриване (lazy deletion).

В опашката може да има повече записи от местата, най-много по един на улица. Цената е малко памет и няколко празни вземания.

const { place, minutes } = queue.poll();
if () continue; // остаряло

Пробвай

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

Колега е решил, че първото намерено време е и най-доброто, както в BFS:

function dijkstra(city, start) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = new MinQueue();
  queue.push({ place: start, minutes: 0 });
  while (queue.size > 0) {
    const { place, minutes } = queue.poll();
    if (minutes > dist.get(place)) continue; // остаряло
    for (const street of city.get(place)) {
      const t = minutes + street.minutes;
      const to = street.to;
      if (!dist.has(to)) {
        dist.set(to, t);
        prev.set(to, place);
        queue.push({ place: to, minutes: t });
      }
    }
  }
  return { dist, prev };
}
const { dist, prev } = dijkstra(city, "Склад");
const r = route(prev, "Клиент");
console.log(`Най-бързо: ${r.join(" → ")} (${r.length - 1} улици, ${minutes(city, r)} мин)`);
Изход
Най-бързо: Склад → Мост → Гара → Клиент (3 улици, 13 мин)

13 минути вместо 9. На кой ред е грешката?

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

Идеята

Колко струва

Всяка улица се пробва два пъти (по веднъж от всеки край) и може да сложи запис. Всеки запис влиза и излиза веднъж, по O(log V). Общо O((V + E) log V) за V места и E улици.

Без опашка най-близкото място се търси с цикъл през всички места, които още не са окончателни. Така е написан алгоритъмът в оригинал:

function dijkstraScan(city, start) {
  const dist = new Map([...city.keys()].map((place) => [place, Infinity]));
  dist.set(start, 0);
  const done = new Set();
  while (done.size < city.size) {
    let best = null;
    for (const place of city.keys()) {
      if (done.has(place)) continue;
      if (best === null || dist.get(place) < dist.get(best)) best = place;
    }
    if (dist.get(best) === Infinity) break;
    done.add(best);
    for (const { to, minutes } of city.get(best)) {
      const t = dist.get(best) + minutes;
      if (t < dist.get(to)) dist.set(to, t);
    }
  }
  return dist;
}
const city = new Map();
addStreet(city, "Склад", "Мост", 2);
addStreet(city, "Склад", "Площад", 5);
addStreet(city, "Склад", "Пазар", 15);
addStreet(city, "Мост", "Площад", 1);
addStreet(city, "Мост", "Гара", 8);
addStreet(city, "Площад", "Гара", 3);
addStreet(city, "Площад", "Пазар", 9);
addStreet(city, "Гара", "Клиент", 3);
addStreet(city, "Пазар", "Клиент", 2);
const dist = dijkstraScan(city, "Склад");
console.log(["Склад", "Мост", "Площад", "Гара", "Пазар", "Клиент"].map((p) => `${p} ${dist.get(p)}`).join(", "));
Изход
Склад 0, Мост 2, Площад 3, Гара 6, Пазар 11, Клиент 9

Отговорът е същият. Но цикълът е V стъпки, и се прави V пъти: O(V²).

Пусни двата варианта в квартал, в който кръстовищата са в мрежа, а всяко е свързано с десния и долния си съсед. Всяка улица е от 1 до 9 минути. Брои се всяко сравнение на две времена: при търсенето на най-близкото, в опашката и при пробването на улица.

  • Без опашка: търсене на най-близкото с цикъл O(n²)
  • С приоритетна опашка O(n log n)
Алгоритъмn = 100n = 1000n = 10 000n = 100 000
Без опашка: търсене на най-близкото с цикъл5410504 372≈ 50 437 200≈ 5 043 720 000
С приоритетна опашка126917 121213 6752 554 618
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
function dijkstra(city, start) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const queue = new MinQueue();
  queue.push({ place: start, minutes: 0 });
  while (queue.size > 0) {
    const { place, minutes } = queue.poll();
    if (minutes > dist.get(place)) continue; // остаряло
    for (const street of city.get(place)) {
      const t = minutes + street.minutes;
      const to = street.to;
      if (!dist.has(to) || t < dist.get(to)) {
        dist.set(to, t);
        prev.set(to, place);
        queue.push({ place: to, minutes: t });
      }
    }
  }
  return { dist, prev };
}

При 1000 кръстовища без опашка са 504 372 сравнения, с опашка 17 121. При 100 000 кръстовища, колкото има един голям град, опашката прави 2 554 618. Без нея биха били около 5 милиарда: Bench не ги пуска, а ги оценява по кривата.

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

Кога O(V²) е по-добре? Когато графът е гъст: всяко място е свързано с почти всяко, и E е около V². Тогава опашката прави O(V² log V), а цикълът O(V²). В пътна мрежа всяко кръстовище има 3–4 улици, графът е рядък и опашката печели.

Отрицателните тегла чупят Dijkstra. Ако една улица струва −5 (да кажем, бонус за доставка по пътя), място, което вече е окончателно, може да стане по-близко през нея по-късно, а алгоритъмът вече не го поглежда. За такива графи е Bellman-Ford: той пробва всяка улица V − 1 пъти, O(V · E), и казва, ако има цикъл, който намалява времето безкрай.

В JavaScript ∞ е Infinity: Infinity + 5 е пак Infinity. В Java и C# ∞ обикновено е най-голямото int, и прибавянето на минути към него дава отрицателно число.

Навигацията в телефона не пуска Dijkstra върху целия континент. Ползва A*: Dijkstra, който в опашката добавя към минутите и оценка колко остава по права линия, затова върви към целта, вместо във всички посоки. Протоколът OSPF, по който рутерите в една мрежа намират пътя на пакетите, пуска истински Dijkstra.

Упражнение

Затворена улица

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

Ремонт. Улицата между моста и площада е затворена. Махни я от града (в двете посоки) и изведи най-бързия маршрут и минутите до гарата, клиента и пазара:

Изход
Гара: Склад → Площад → Гара (8 мин)
Клиент: Склад → Площад → Гара → Клиент (11 мин)
Пазар: Склад → Площад → Гара → Клиент → Пазар (13 мин)

Пазарът пак е най-бърз през клиента: 13 минути срещу 14 през площада и 15 по булеварда.

Още задачи

  • Спри навреме. Ако те интересува само клиентът, спри, щом той излезе от опашката. Колко записа остават невзети?
  • Брой вземанията. Брой колко записа са излезли от опашката и колко от тях са остарели.
  • Два куриера. Два склада, един клиент: кой куриер стига пръв? Подсказка: сложи и двата склада в опашката с 0 минути.

Тест

Провери се

1. Защо BFS не намира най-бързия маршрут, когато улиците имат минути?
2. Мястото излиза от опашката с най-малко минути от всички записи. Защо времето му е окончателно?
3. В опашката стои 5 Площад, а Площад вече има 3 минути. Какво прави алгоритъмът, когато 5 Площад излезе?
4. Колко струва Dijkstra с двоичен heap за V места и E улици?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·