Eng qisqa yo'l: BFS, Dijkstra algoritmi va Bellman-Ford g'oyasi

Qisqacha: Vaznsiz grafda eng kam qirrali yo'lni BFS topadi — har tugunga birinchi yetib kelgan yo'l eng qisqasi. Vaznli grafda (daqiqa, narx) Dijkstra algoritmi kerak: u har safar eng yaqin, hali yakunlanmagan tugunni olib, qo'shnilarigacha vaqtni yaxshilaydi. Ustuvor navbat (heap) bilan u O((V + E) log V) ishlaydi. Yo'lning o'zi prev jadvali bo'yicha orqaga yurib tiklanadi. Manfiy vaznlarda Dijkstra xato qiladi — u yerda Bellman-Ford O(V · E) ishlatiladi.

Bu darsda

• Vaznsiz grafda BFS bilan eng qisqa yo'lni va yo'lning o'zini topa olasiz.
• Dijkstra algoritmini heap bilan yoza olasiz va uning qadamlarini qo'lda kuzata olasiz.
• Nega Dijkstra O((V + E) log V) ekanini va heapsiz versiya O(V²) ekanini o'lchov bilan ko'rsata olasiz.
• Manfiy vaznda Dijkstra nega xato qilishini tushuntira olasiz va Bellman-Ford g'oyasini bilasiz.

Oldin bilishingiz kerak: Graflarda BFS va DFS, Graf atamalari va ko'rinishlari, Heap, Priority queue va heap naqshlari.

1. Nega bu kerak?

Endi Jasur aka asosiy savolni berdi: "Kuryer Bahor'dan Qo'yliq'ga eng tez qaysi yo'l bilan boradi?"

O'tgan darsda BFS Qo'yliq'ni 2-qatlamga qo'ydi: Bahor → Mirobod → Qo'yliq. Ikkita yo'l — eng kami shu. Lekin xaritadagi daqiqalarni qo'shib ko'ring: 6 + 13 = 19 daqiqa. Boshqa yo'l: Bahor → Mirobod → Sergeli → Qo'yliq. Uchta yo'l, lekin 6 + 9 + 3 = 18 daqiqa. Kamroq chorraha — tezroq degani emas.

Demak, ikki xil "eng qisqa" bor. Eng kam qirrali — har yo'l bir xil "qimmat" bo'lganda (metro bekatlari, do'stlik zanjiri). Eng kam vaznli — yo'llar har xil uzunlikda bo'lganda (daqiqa, kilometr, so'm). Birinchisini BFS yechadi. Ikkinchisi uchun bugun yangi algoritm o'rganamiz.

Bu darsga oldin va'da ham berilgan edi. Asosiy murakkablik sinflari darsida kuryer hamma manzillarni aylanib chiqadigan eng yaxshi tartibni qidirish O(n!) ekanini ko'rdik. U boshqa masala. Bugungisi — ikki nuqta orasidagi eng tez yo'l. Bu masala ancha "yumshoq": uni xaritaning o'lchamiga deyarli chiziqli vaqtda yechish mumkin.

2. Vaznsiz graf: BFS va yo'lni tiklash

2.1 prev — "kimdan keldim"

BFS har tugunga eng kam qirrali yo'l bilan birinchi bo'lib yetib keladi. Tugunning qatlami — masofa. Lekin kuryerga masofa emas, yo'l kerak: qaysi chorrahalardan o'tadi.

Buning uchun har tugun uchun bitta narsani eslab qolamiz — uni kim topdi. Buni prev (inglizcha "previous" — oldingi) deb ataymiz. Sergeli'ni Bahor topgan bo'lsa, prev.get("S") — "B". Yo'lni tiklash uchun nishondan boshlab prev bo'yicha orqaga yuramiz, toki boshlang'ich tugunga yetguncha. Keyin ro'yxatni ag'daramiz.

Bu non bo'laklari bilan yo'l belgilashga o'xshaydi. Ertakdagi bolalar har burilishda non ushog'ini tashlab ketgan. Uyga qaytish uchun ushoqlar bo'yicha orqaga yurishgan. prev — har chorrahadagi ushoq: "bu yerga qayerdan keldim".

const graph = new Map(Object.entries({
  B: ["C", "O", "M", "S"], C: ["B", "O", "S"], O: ["B", "C", "Y"],
  M: ["B", "Y", "S", "Q"], S: ["B", "C", "M", "Q"], Y: ["O", "M"],
  Q: ["M", "S"],
}));

function fewestRoads(graph, start, target) {
  const prev = new Map([[start, null]]); // ham visited, ham "kimdan"
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const v = queue[head++];
    if (v === target) break; // yetib keldik
    for (const u of graph.get(v)) {
      if (!prev.has(u)) {
        prev.set(u, v);
        queue.push(u);
      }
    }
  }
  if (!prev.has(target)) return []; // yetib bo'lmaydi
  const path = [];
  for (let v = target; v !== null; v = prev.get(v)) path.push(v);
  return path.reverse();
}
console.log(fewestRoads(graph, "B", "Q")); // [ 'B', 'M', 'Q' ]
console.log(fewestRoads(graph, "Y", "C")); // [ 'Y', 'O', 'C' ]

Yangi narsalar:

• prev uchta vazifani bajaradi: "kimdan keldim" ni saqlaydi, visited o'rnini bosadi (prev.has(u)) va boshlang'ich tugunni null bilan belgilaydi.
• if (v === target) break — nishon navbatdan chiqdi, demak unga eng qisqa yo'l allaqachon ma'lum. Qolgan xaritani aylanish shart emas.
• Oxirgi for — Q dan boshlab: Q → M (Q ni M topgan) → B (M ni B topgan) → null. To'plangan ["Q", "M", "B"] ni reverse() ag'daradi.

Murakkablik — oddiy BFS kabi: O(V + E). Yo'lni tiklash — yo'l uzunligicha qadam, eng ko'pi bilan O(V).

Tekshirib ko'ring: fewestRoads(graph, "B", "B") nima qaytaradi? Kodni qatorma-qator kuzating.

3. Vaznli graf: sodda yechim

3.1 Hamma yo'llarni sinash

Daqiqalar har xil bo'lsa-chi? Birinchi xayolga keladigan yechim — brute force: Bahor'dan Qo'yliq'ga olib boradigan hamma yo'llarni (bitta mahallaga ikki marta kirmasdan) DFS bilan sanab chiqish va eng tezini tanlash. Bu Backtracking darsidagi "tanla → o'rgan → bekor qil" naqshi.

Bizning xaritada bunday yo'llar 14 ta — eng tezi 18 daqiqa (B → M → S → Q). Kichik xaritada bu ishlaydi. Lekin yo'llar soni qanday o'sishini ko'ring. Kvadrat panjara shaklidagi shaharda (k × k chorraha) burchakdan qarama-qarshi burchakkacha yo'llar sonini o'zimiz DFS bilan sanadik:

6 × 6 da — bir milliondan ko'p, sanash 0,6 soniya oldi. 7 × 7 da (49 chorraha) yo'llar soni 575 milliondan oshadi (OEIS A007764 ketma-ketligi). Toshkentning minglab chorrahasi uchun bu yo'l butunlay yopiq: yo'llar soni eksponensial o'sadi.

3.2 Nima ortiqcha?

Brute force bir xil ishni qayta-qayta qiladi. Masalan, Mirobod'gacha eng tez yo'l — 6 daqiqa (to'g'ri). Mirobod orqali o'tadigan har bir yo'l Mirobod'gacha qismini qayta hisoblaydi. Undan ham yomoni — Mirobod'ga 20 daqiqada keladigan yo'llarni ham oxirigacha davom ettiradi, vaholanki ular hech qachon eng tezi bo'lolmaydi.

Bundan muhim xulosa chiqadi: eng qisqa yo'lning har bir bo'lagi ham eng qisqa yo'l. Agar B → M → S → Q eng tez bo'lsa, uning boshi B → M → S ham Sergeli'gacha eng tez yo'l. Aks holda Sergeli'ga tezroq yo'l bilan borib, undan Qo'yliq'ga o'tib, umumiy vaqtni qisqartirgan bo'lardik. Bu kuzatish Dijkstra'ning asosi.

4. Dijkstra algoritmi

4.1 G'oya

Dijkstra algoritmi (Dijkstra's algorithm) — manfiy bo'lmagan vaznli grafda bitta tugundan qolgan hammasigacha eng qisqa yo'llarni topadigan algoritm. Uni gollandiyalik olim Edsger Dijkstra 1956 yilda o'ylab topgan. O'qilishi — "deykstra".

Uning g'oyasi BFS'dagi to'lqinga o'xshaydi, faqat to'lqin daqiqalar bo'yicha tarqaladi:

1. Har tugun uchun "hozircha ma'lum eng yaxshi vaqt" ni saqlaymiz (dist). Boshida: boshlang'ich tugun — 0, qolganlari — ∞ (hali yo'l ma'lum emas).
2. Hali yakunlanmagan tugunlar ichidan dist i eng kichigini olamiz. Uning vaqti endi aniq — uni yakunlangan deb belgilaymiz.
3. Uning har qo'shnisi uchun tekshiramiz: shu tugun orqali borish tezroqmi? dist[v] + vazn < dist[u] bo'lsa — dist[u] ni yangilaymiz.
4. 2-qadamga qaytamiz, toki hamma tugun yakunlanguncha.

Uchinchi qadam o'z nomiga ega — relaksatsiya (relaxation), ya'ni "yo'lni yaxshilash": qirra orqali ma'lum vaqtni kamaytirishga urinish.

4.2 Nega eng kichigi aniq?

Ikkinchi qadamdagi da'vo — algoritmning yuragi. Mirobod'ning dist i 6, va yakunlanmaganlar orasida eng kichigi. Unga 6 dan tezroq yo'l bormi?

Bunday yo'l bo'lsa, u qaysidir boshqa yakunlanmagan tugundan o'tishi kerak. Lekin u tugunlarning har biriga yetishning o'zi kamida 6 daqiqa (6 — eng kichigi edi). Undan keyin yana yo'l bor, vaznlar esa manfiy emas — vaqt faqat ko'payadi yoki joyida qoladi. Demak, aylanma yo'l 6 dan kam bo'la olmaydi. Mirobod'ning javobi — aniq.

Shu sababli Dijkstra ochko'z (greedy) algoritm deyiladi: har qadamda hozir eng yaxshi ko'ringan tanlovni qiladi va uni qayta ko'rib chiqmaydi. Bu yerda ochko'z tanlov to'g'ri ekanini isbotladik. Hamma masalada ham bunday emas — buni Greedy algoritmlar darsida ko'ramiz.

4.3 Heap — eng kichigini tez olish

"Yakunlanmaganlar ichidan eng kichigini olish" ni har safar butun ro'yxatni ko'rib chiqib bajarsak, bitta qadam O(V), jami O(V²). Eng kichigini tez beradigan tuzilmani esa bilamiz — ustuvor navbat (priority queue), ichida heap. Unga [vaqt, tugun] juftlarini qo'yamiz. pop() doim eng kichik vaqtli juftni O(log V) da qaytaradi.

Bitta nozik joy. Sergeli'ning vaqti avval 16 edi, keyin 15 ga yaxshilandi. Heap ichidagi elementni "joyida" o'zgartirish qiyin. Shuning uchun oddiy yo'l tutamiz: yangi juft [15, "S"] ni qo'shamiz, eskisi [16, "S"] ichkarida qoladi. U keyinroq chiqqanda, S allaqachon yakunlangan bo'ladi — uni shunchaki tashlab yuboramiz. Bunday yozuvni eskirgan (stale) yozuv deyishadi. Usulning nomi — "dangasa o'chirish" (lazy deletion).

4.4 Qadamma-qadam

Quyida Dijkstra Bahor'dan boshlanadi. Tugun ostidagi son — hozircha ma'lum eng yaxshi vaqt. Yashil tugun — yakunlangan, sariq — vaqti bor, lekin hali yakunlanmagan. Navbat qatorida heap ichidagi yozuvlar, eng kichigi chapda (S:15 — "Sergeli, 15 daqiqa"). Sergeli'ga e'tibor bering: avval to'g'ri yo'l bilan 16 oladi, keyin Mirobod orqali 15 ga yaxshilanadi.

Ketma-ketlikka qarang: tugunlar vaqt bo'yicha yakunlandi — 0, 6, 7, 9, 11, 15, 18. Dijkstra hech qachon uzoqroq tugunni yaqinroqdan oldin yakunlamaydi. Ikki marta eskirgan yozuv chiqdi (S:16 va Q:19) — ular hech narsani buzmadi, faqat ozgina ortiqcha ish.

4.5 To'liq kod

Endi hammasi birga: heap klassi (Heap darsidagi bilan bir xil g'oya, faqat elementlar [vaqt, tugun] juftlari va ular [0] — vaqt bo'yicha solishtiriladi), xarita, Dijkstra va yo'lni tiklash:

class MinHeap {
  #a = [];
  get size() { return this.#a.length; }
  push(item) {
    const a = this.#a;
    a.push(item);
    let i = a.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2); // ota
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.#a;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      while (true) {
        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;
  }
}

const roads = [["B", "C", 7], ["B", "O", 9], ["B", "M", 6],
  ["B", "S", 16], ["C", "O", 10], ["C", "S", 9], ["O", "Y", 11],
  ["Y", "M", 5], ["M", "S", 9], ["M", "Q", 13], ["S", "Q", 3]];
const graph = new Map();
for (const [a, b, w] of roads) {
  if (!graph.has(a)) graph.set(a, []);
  if (!graph.has(b)) graph.set(b, []);
  graph.get(a).push([b, w]);
  graph.get(b).push([a, w]);
}

function dijkstra(graph, start) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const heap = new MinHeap();
  heap.push([0, start]);
  const done = new Set();
  while (heap.size > 0) {
    const [d, v] = heap.pop();
    if (done.has(v)) continue; // eskirgan yozuv
    done.add(v);
    for (const [u, w] of graph.get(v)) {
      const nd = d + w;
      if (nd < (dist.get(u) ?? Infinity)) {
        dist.set(u, nd);
        prev.set(u, v);
        heap.push([nd, u]);
      }
    }
  }
  return { dist, prev };
}

function pathTo(prev, target) {
  const path = [];
  for (let v = target; v !== undefined; v = prev.get(v)) path.push(v);
  return path.reverse(); // oxiridan boshiga yig'dik — ag'daramiz
}

const { dist, prev } = dijkstra(graph, "B");
console.log(dist);
console.log(pathTo(prev, "Q").join(" -> "), dist.get("Q"));

Konsolda:

Map(7) {
  'B' => 0,
  'C' => 7,
  'O' => 9,
  'M' => 6,
  'S' => 15,
  'Y' => 11,
  'Q' => 18
}
B -> M -> S -> Q 18

Kodning yangi qismlari:

• #a — klassning xususiy maydoni (private field): tashqaridan heap.#a deb o'qib bo'lmaydi. Heap tartibini faqat push va pop buzmasdan saqlaydi.
• get size() — getter: heap.size ni xususiyat kabi o'qiymiz, qavssiz.
• Math.floor((i - 1) / 2) — ota indeksi, 2 * i + 1 va 2 * i + 2 — bolalar (Heap darsidagi formulalar).
• dist.get(u) ?? Infinity — tugun hali dist da bo'lmasa, uning vaqti cheksiz deb olinadi.
• pathTo — BFS'dagi bilan bir xil: prev bo'yicha orqaga, keyin reverse().

dist faqat bitta Qo'yliq uchun emas, hamma mahallalar uchun eng tez vaqtni berdi. Dijkstra bitta ishga tushishda "Bahor'dan hamma joyga" savoliga javob beradi. Faqat bitta nishon kerak bo'lsa, nishon navbatdan chiqqanda to'xtash mumkin — 3-mashqda shunday qilasiz.

Tekshirib ko'ring: Mirobod–Sergeli yo'lida ta'mirlash boshlandi, endi u 12 daqiqa. Bahor'dan Qo'yliq'ga eng tez yo'l qanday bo'ladi?

5. Murakkablik va o'lchov

5.1 Hisob

Har tugun bir marta yakunlanadi va uning qo'shnilar ro'yxati bir marta aylaniladi — jami O(V + E) qirra tekshiruvi. Har muvaffaqiyatli relaksatsiya heap'ga bitta push qiladi — eng ko'pi bilan E ta. Heap'da eng ko'pi bilan E ta yozuv bor, har push/pop O(log E). E ≤ V² bo'lgani uchun log E ≤ log V² = 2 log V (logarifm darajani oldinga chiqaradi), ya'ni O(log V) — Big-O 2 ni tashlab yuboradi. Jami: O((V + E) log V). Xotira — O(V + E): dist, prev va heap.

Heapsiz versiyada esa har qadamda yakunlanmagan hamma tugunlar ichidan eng kichigini qidiramiz: V qadam × V tekshiruv = O(V²). Zich grafda (E ≈ V²) bu hatto yaxshiroq — log yo'q. Siyrak grafda esa heap ancha tez.

5.2 O'lchov

Ikkala versiyani siyrak grafda o'lchadik (har tugundan 2 ta tasodifiy qirra, vaznlar 1–20, urug'li generator; har V alohida jarayonda, isitish va mediana — benchmarking usuli). Raqamlar taxminiy.

Heap bilan:

Heapsiz (har safar eng kichigini massivdan qidirish):

Heap bilan V ikki baravar oshganda vaqt taxminan 2,2 baravar oshdi. Ikkidan biroz ortig'i — log V ko'paytuvchisi: V ×2 bo'lsa, log V bor-yo'g'i bir pog'onaga oshadi. Heapsiz versiyada nisbat 4 dan ham katta. Nazariya ×4 deydi, ortig'i esa protsessorning ishi: har qadamda 16 000 elementli massivni boshidan oxirigacha qayta o'qish xotira tezligiga tiraladi. Asosiy xulosa o'zgarmaydi — o'sish kvadratik.

16 000 tugunda heapsiz versiya 0,87 soniya ishladi. Heap versiyasi 50 baravar katta xaritani (800 000) 1,4 soniyada yechdi.

6. Manfiy vaznlar va Bellman-Ford

6.1 Dijkstra qayerda adashadi

Endi vaznlar pul bo'lsin — kuryerning yoqilg'i xarajati, ming so'mda. Bitta yo'lda kuryer ziravor bozoridan (Z) Bahor uchun xarid qiladi va do'kon (D) unga 2 000 so'm keshbek beradi. Shu qirraning vazni manfiy: −2. Yo'llar bir tomonlama (yo'nalgan graf):

• B → Z: 3, B → D: 2, Z → D: −2, D → K (mijoz): 1.

To'g'ri javob: B → Z → D → K = 3 − 2 + 1 = 2. Dijkstra nima deydi?

// Dijkstra (darsdagi kod) yo'nalgan grafda:
// B: Z, D | Z: D(-2) | D: K
console.log(dijkstra(graph, "B").dist);
// Map(4) { 'B' => 0, 'Z' => 3, 'D' => 1, 'K' => 3 }

K uchun 3 chiqdi — xato. Nima bo'ldi? Dijkstra D ni 2 bilan yakunladi (Z dan oldin, chunki 2 < 3) va darhol K ni 2 + 1 = 3 deb hisobladi. Keyin Z chiqdi va D ni 1 ga tushirdi — lekin D allaqachon yakunlangan edi, uning qo'shnilari qayta yangilanmadi. "Eng kichigi aniq" degan isbot vaznlar manfiy emasligiga tayangan edi. Bu shart buzildi — algoritm ham buzildi.

6.2 Bellman-Ford g'oyasi

Bellman-Ford algoritmi — manfiy vaznlar bilan ham ishlaydigan eng qisqa yo'l algoritmi. Uning g'oyasi juda sodda: hamma qirralarni ketma-ket relaksatsiya qilamiz va buni V − 1 marta takrorlaymiz.

Nega V − 1? Siklsiz eng qisqa yo'lda eng ko'pi bilan V − 1 ta qirra bor. Birinchi aylanishdan keyin 1 qirrali eng qisqa yo'llar to'g'ri bo'ladi, ikkinchisidan keyin — 2 qirralilar, va hokazo. V − 1 aylanishdan keyin hammasi to'g'ri.

const nodes = ["B", "Z", "D", "K"];
const edges = [
  ["B", "Z", 3], ["B", "D", 2], ["Z", "D", -2], ["D", "K", 1],
];

function bellmanFord(nodes, edges, start) {
  const dist = new Map(nodes.map((v) => [v, Infinity]));
  dist.set(start, 0);
  for (let round = 1; round < nodes.length; round++) { // V - 1 marta
    for (const [a, b, w] of edges) {
      if (dist.get(a) + w < dist.get(b)) dist.set(b, dist.get(a) + w);
    }
  }
  for (const [a, b, w] of edges) { // yana bir marta: hali kamayadimi?
    if (dist.get(a) + w < dist.get(b)) return null; // manfiy sikl
  }
  return dist;
}
console.log(bellmanFord(nodes, edges, "B"));
edges.push(["D", "Z", 1]); // Z -> D -> Z: -2 + 1 = -1, manfiy sikl
console.log(bellmanFord(nodes, edges, "B"));

Konsolda:

Map(4) { 'B' => 0, 'Z' => 3, 'D' => 1, 'K' => 2 }
null

K uchun to'g'ri javob — 2. Infinity + w ham Infinity qoladi, shuning uchun hali yetib borilmagan tugundan relaksatsiya hech narsani buzmaydi.

Ikkinchi chaqiruvda D → Z yo'li qo'shildi. Endi Z → D → Z aylanasi −1 so'm "foyda" beradi. Bu manfiy sikl: uni har aylanganda yo'l arzonlashadi, demak "eng arzon yo'l" umuman yo'q — cheksiz aylanib, xohlagancha kamaytirish mumkin. Bellman-Ford buni ushlaydi: V − 1 aylanishdan keyin ham biror qirra vaqtni kamaytirsa, manfiy sikl bor. Funksiya null qaytardi.

Narxi — O(V · E): V − 1 aylanish, har birida E ta qirra. Dijkstra'dan ancha sekin. Shuning uchun qoida oddiy: vaznlar manfiy emas — Dijkstra; manfiy vazn bor — Bellman-Ford.

Tekshirib ko'ring: Hamma vaznlarga bir xil son qo'shsak (masalan, +2), manfiy vaznlar yo'qoladi va Dijkstra ishlatsa bo'ladi. Bu fikrda nima xato?

7. Qaysi algoritmni tanlash

Yana ikkita nomni eshitasiz. Hamma juftlar orasidagi eng qisqa yo'llar uchun Floyd-Warshall algoritmi bor — O(V³), kichik graflar uchun. Xaritalarda esa Dijkstra'ning "aqlli" ko'rinishi — A* ("A yulduz") ishlatiladi: u nishon tomonga qarab yo'nalgan qidiradi va keraksiz tomonlarni kamroq ochadi.

8. Chegaraviy holatlar

• Boshlang'ich = nishon. Javob 0, yo'l — bitta tugun.
• Yetib bo'lmaydigan tugun. dist da u yo'q (yoki ∞). pathTo uchun avval tekshiring — aks holda faqat nishondan iborat noto'g'ri "yo'l" qaytadi.
• Nol vaznli qirra. Dijkstra uchun muammo emas: shart — manfiy bo'lmaslik.
• Bir xil vaqtli bir nechta yo'l. Javob (vaqt) bitta, yo'l esa bir nechta bo'lishi mumkin.
• Ikki tugun orasida ikkita qirra (eski va yangi ko'prik). Dijkstra o'zi kichigini tanlaydi — har ikkisi relaksatsiya qilinadi.
• Juda katta vaznlar. Yig'indilar Number.MAX_SAFE_INTEGER dan oshmasin; vaqt yoki pul uchun bu kamdan-kam muammo.

9. Ko'p uchraydigan xatolar

9.1 Vaznli grafda BFS

"BFS eng qisqa yo'lni topadi" — faqat vaznsiz grafda. Bahor → Qo'yliq uchun BFS 19 daqiqalik yo'lni berdi, to'g'risi — 18. Tuzatish: vaznlar har xil bo'lsa — Dijkstra.

9.2 Eskirgan yozuvni tekshirmaslik

if (done.has(v)) continue qatorini olib tashlasangiz, natija to'g'ri chiqadi, lekin eskirgan yozuvlar ham qo'shnilarini qayta aylanib chiqadi. Zich grafda bu ish hajmini keskin oshiradi. Tuzatish: heap'dan chiqqan yozuvni har doim tekshiring — done to'plami yoki d > dist.get(v) sharti bilan.

9.3 Yakunlashni push paytida qilish

"Qo'shnini heap'ga qo'yganda uni yakunlangan deb belgilayman" — BFS odatini Dijkstra'ga ko'chirish. Bu noto'g'ri: Sergeli 16 bilan qo'yilgan, keyin 15 topilgan. Tuzatish: Dijkstra'da tugun heap'dan chiqqanda yakunlanadi (BFS'da esa navbatga qo'yganda belgilanadi — farqni eslab qoling).

9.4 Manfiy vazn bilan Dijkstra

Xato xabari chiqmaydi — shunchaki noto'g'ri raqam. Bu eng xavfli xato turi. Tuzatish: vaznlarni tekshiring; manfiy bo'lsa — Bellman-Ford.

10. Mashqlar

1-mashq (oson): Dijkstra jadvali

Darsdagi xaritada Dijkstra'ni Sergeli'dan (S) boshlang. Tugunlar qaysi tartibda yakunlanadi va har biriga eng tez vaqt qancha?

2-mashq (o'rta): Kam chorraha yoki kam daqiqa

Kuryer mototsikli har chorrahada to'xtaydi va har to'xtash 4 daqiqa yo'qotadi. Bahor → Qo'yliq uchun ikki yo'lni solishtiring: B → M → Q (2 qirra) va B → M → S → Q (3 qirra). Endi qaysi tezroq? Buni grafda qanday hisobga olish mumkin?

3-mashq (qiyin): Yo'l topuvchi va testlar

kurs/mashqlar/14/47-eng-qisqa-yol/yol.test.mjs faylida shortestPath(graph, start, target) funksiyasini yozing. U { time, path } qaytarsin; nishonga yetib bo'lmasa — { time: Infinity, path: [] }. Nishon heap'dan chiqqanda to'xtasin (erta to'xtash). To'rtta test (node:test):

1. O'zidan o'ziga — { time: 0, path: ["B"] }.
2. Bahor → Qo'yliq — 18 daqiqa, ["B", "M", "S", "Q"].
3. Yo'li yo'q filial — Infinity.
4. Nol vaznli qirra ham to'g'ri hisoblanadi.

// kurs/mashqlar/14/47-eng-qisqa-yol/yol.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

class MinHeap {
  #a = [];
  get size() { return this.#a.length; }
  push(item) {
    const a = this.#a;
    a.push(item);
    let i = a.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2); // ota
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.#a;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      while (true) {
        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 shortestPath(graph, start, target) {
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const heap = new MinHeap();
  heap.push([0, start]);
  const done = new Set();
  while (heap.size > 0) {
    const [d, v] = heap.pop();
    if (done.has(v)) continue;
    if (v === target) break; // nishon yakunlandi — erta to'xtash
    done.add(v);
    for (const [u, w] of graph.get(v)) {
      const nd = d + w;
      if (nd < (dist.get(u) ?? Infinity)) {
        dist.set(u, nd);
        prev.set(u, v);
        heap.push([nd, u]);
      }
    }
  }
  if (!dist.has(target)) return { time: Infinity, path: [] };
  const path = [];
  for (let v = target; v !== undefined; v = prev.get(v)) path.push(v);
  return { time: dist.get(target), path: path.reverse() };
}

function buildMap(roads) {
  const graph = new Map();
  for (const [a, b, w] of roads) {
    if (!graph.has(a)) graph.set(a, []);
    if (!graph.has(b)) graph.set(b, []);
    graph.get(a).push([b, w]);
    graph.get(b).push([a, w]);
  }
  return graph;
}

const city = buildMap([
  ["B", "C", 7], ["B", "O", 9], ["B", "M", 6], ["B", "S", 16],
  ["C", "O", 10], ["C", "S", 9], ["O", "Y", 11], ["Y", "M", 5],
  ["M", "S", 9], ["M", "Q", 13], ["S", "Q", 3],
]);

test("o'zidan o'ziga — 0 daqiqa", () => {
  const r = shortestPath(city, "B", "B");
  assert.deepEqual(r, { time: 0, path: ["B"] });
});

test("Bahor → Qo'yliq: 18 daqiqa, M va S orqali", () => {
  const r = shortestPath(city, "B", "Q");
  assert.equal(r.time, 18);
  assert.deepEqual(r.path, ["B", "M", "S", "Q"]);
});

test("yetib bo'lmaydigan tugun — Infinity", () => {
  const g = buildMap([["B", "C", 7]]);
  g.set("N", []); // yo'li yo'q filial
  const r = shortestPath(g, "B", "N");
  assert.deepEqual(r, { time: Infinity, path: [] });
});

test("nol vaznli qirra ham ishlaydi", () => {
  const g = buildMap([["B", "C", 0], ["C", "Q", 5], ["B", "Q", 6]]);
  assert.deepEqual(shortestPath(g, "B", "Q").path, ["B", "C", "Q"]);
});

✔ o'zidan o'ziga — 0 daqiqa (1.3942ms)
✔ Bahor → Qo'yliq: 18 daqiqa, M va S orqali (0.25ms)
✔ yetib bo'lmaydigan tugun — Infinity (0.1538ms)
✔ nol vaznli qirra ham ishlaydi (0.1883ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 106.8465

4-mashq: Amaliy tajriba — murakkablik jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga qo'shing: BFS bilan eng qisqa yo'l, Dijkstra (heap va massiv bilan), Bellman-Ford, hamma yo'llarni sanash (brute force). Har qatorga qachon ishlatilishini bir so'z bilan yozing.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Eng kam qirrali yo'l | BFS + prev | O(V + E) | O(V) |
| Eng tez yo'l, vazn ≥ 0 | Dijkstra + heap | O((V + E) log V) | O(V + E) |
| Eng tez yo'l, zich graf | Dijkstra massiv bilan | O(V²) | O(V) |
| Eng tez yo'l, manfiy vazn | Bellman-Ford | O(V · E) | O(V) |
| Eng tez yo'l | hamma yo'llar (DFS) | eksponensial | O(V) |

git add 14/MURAKKABLIK.md 14/47-eng-qisqa-yol
git commit -m "14/47: Dijkstra — jadval va shortestPath testlari"

11. Real ishda

• Navigatsiya. Xarita ilovalari yo'lni Dijkstra'ning tezlashtirilgan ko'rinishlari (A*, oldindan hisoblangan "magistral" qatlamlar) bilan topadi. Vazn — tirbandlikni hisobga olgan vaqt, u har daqiqa yangilanadi.
• Internet marshrutlash. Routerlar paketni qaysi yo'ldan yuborishni hal qiladi. OSPF protokoli har router ichida Dijkstra'ni ishga tushiradi; RIP protokoli esa Bellman-Ford g'oyasiga asoslangan.
• Yetkazish xizmatlari. "Kuryerdan restoranga, restorandan mijozga" vaqtini baholash — eng qisqa yo'l so'rovlari. Ular sekundiga minglab bajariladi, shuning uchun algoritm narxi to'g'ridan-to'g'ri server xarajatiga aylanadi.
• O'yinlar. Kompyuter boshqaradigan qahramonlar xaritada A* bilan yo'l topadi.
• Intervyu. "Network Delay Time" (LeetCode 743), "Cheapest Flights Within K Stops" (787) — Dijkstra va Bellman-Ford masalalari. Doim aytish kerak: vaznlar manfiy emasmi?

Xulosa

• Vaznsiz grafda eng qisqa yo'l — BFS; yo'lning o'zi prev bo'yicha orqaga yurib tiklanadi.
• Kam qirra ≠ kam vaqt: Bahor → Qo'yliq BFS bo'yicha 19, Dijkstra bo'yicha 18 daqiqa.
• Dijkstra eng yaqin yakunlanmagan tugunni oladi va qo'shnilarini relaksatsiya qiladi; heap bilan O((V + E) log V). O'lchovda V ×2 → vaqt ≈ ×2,2; heapsiz O(V²) versiya — ×4 dan ham ko'p.
• Tugun heap'dan chiqqanda yakunlanadi; eskirgan yozuvlar tashlab yuboriladi.
• Manfiy vaznda Dijkstra jim xato qiladi. Bellman-Ford O(V · E) to'g'ri hisoblaydi va manfiy siklni topadi.

Keyingi dars: Topologik saralash va sikl aniqlash — yo'nalgan grafda ishlarni to'g'ri tartibda bajarish (osh retsepti, paket bog'liqliklari), Kahn algoritmi va rangli DFS.

Manbalar

• Edsger W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik 1, 1959, 269–271-betlar.
• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 22-bob (bitta manbadan eng qisqa yo'llar: Bellman-Ford, Dijkstra).
• OEIS A007764 — panjarada burchakdan burchakka o'z-o'zini kesmaydigan yo'llar soni — oeis.org/A007764
• LeetCode 743 "Network Delay Time" — leetcode.com/problems/network-delay-time