24-dars: Dijkstra

3-darajaOltin — graflar17–24 darslar

HayotdaYo'l

Toshkentdan Samarqandga borishning bir necha yo’li bor. Eng kam shaharlardan o’tadigan yo’l eng arzoni bo’lishi shart emas: to’g’ri yo’l tor va sekin, aylanma esa keng va tez bo’lishi mumkin. Qadamlarni sanash yetmaydi — narxni qo’shish kerak.

Bu darsdan keyin siz

• vaznli grafda eng arzon yo’lni Dijkstra bilan topasiz
• uyum nima uchun kerakligini tushuntirasiz
• manfiy vaznda usul nega buzilishini misolda ko’rsatasiz

Avval qo’lda

Avval qo‘lda

~7 daqiqa·juftlikda·Qog'oz va qalam

Beshta shahar chizing va ular orasiga narxlar yozilgan yo’llar tortining. Bitta shaharni «uy» deb belgilang.

Har shahar yoniga qalam bilan hozirgi eng arzon narxni yozing. Qoida: narxi eng kichik va hali qora ranglanmagan shaharni tanlang, uni qora bilan ustidan yozing va qo’shnilarining narxini yangilang.

Nimani sezishingiz kerak

Qora ranglangan shaharning narxi boshqa hech qachon o’zgarmadi. Nega: narxlar musbat, demak boshqa yo’l bilan kelish faqat qimmatroq bo’lishi mumkin.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Nega BFS yetmaydi

BFS qirralar sonini sanaydi. Vaznli grafda esa ikki qirrali yo’l bir qirrali yo’ldan arzon bo’lishi mumkin — vizualdagi grafda 1 → 3 → 2 narxi 3, to’g’ridan-to’g’ri 1 → 2 esa 4.

DijkstraDijkstra's algorithm

Musbat vaznli grafda bitta uchdan barcha uchlargacha eng arzon yo’lni topadigan algoritm. Har qadamda eng arzon tugallanmagan uch olinadi.

Sekin yechim

Hech qanday tartib tanlamaymiz: barcha qirralar bo’ylab yurib narxlarni yaxshilaymiz va hech narsa o’zgarmaguncha takrorlaymiz.

sekin.pyNusxalash

1n = 52qirralar = [(1, 2, 4), (1, 3, 2), (2, 3, 1), (2, 4, 5), (3, 4, 8), (4, 5, 3)]3CHEKSIZ = float("inf")4masofa = [CHEKSIZ] * (n + 1)5masofa[1] = 06ozgardi = True7while ozgardi:8  ozgardi = False9  for a, b, w in qirralar:10      if masofa[a] + w < masofa[b]:11          masofa[b] = masofa[a] + w12          ozgardi = True13      if masofa[b] + w < masofa[a]:14          masofa[a] = masofa[b] + w15          ozgardi = True16print(masofa[1:])

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1n = 52qirralar = [(1, 2, 4), (1, 3, 2), (2, 3, 1), (2, 4, 5), (3, 4, 8), (4, 5, 3)]3CHEKSIZ = float("inf")4masofa = [CHEKSIZ] * (n + 1)5masofa[1] = 06ozgardi = True7while ozgardi:8  ozgardi = False9  for a, b, w in qirralar:10      if masofa[a] + w < masofa[b]:11          masofa[b] = masofa[a] + w12          ozgardi = True13      if masofa[b] + w < masofa[a]:14          masofa[a] = masofa[b] + w15          ozgardi = True16print(masofa[1:])

Sizning bashoratingizTekshirish

Javobni ko'rish

[0, 3, 2, 8, 11]

2-uchga to'g'ridan-to'g'ri 4 turadi, lekin 3 orqali 2 + 1 = 3. Bu yechim manfiy vaznda ham to'g'ri ishlaydi — shuning uchun u ishonchli etalon.

Nega sekin

Har o’tishda kamida bitta uch o’z yakuniy narxini oladi, ya’ni eng yomon holatda n marta o’tish kerak.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 100 000
Takror-takror yaxshilashn^2	10⁶sig‘adi	10¹⁰sig‘maydi
Dijkstra + uyumn log n	9 966sig‘adi	10⁶sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

Dijkstra to’g’ri tartibni tanlaydi: har qadamda eng arzon tugallanmagan uchni oladi. Uyum shu uchni qidirmasdan beradi.

tez.pyNusxalash

1import heapq2n = 53qirralar = [(1, 2, 4), (1, 3, 2), (2, 3, 1), (2, 4, 5), (3, 4, 8), (4, 5, 3)]4qoshni = [[] for _ in range(n + 1)]5for a, b, w in qirralar:6  qoshni[a].append((b, w))7  qoshni[b].append((a, w))8CHEKSIZ = float("inf")9masofa = [CHEKSIZ] * (n + 1)10masofa[1] = 011tugadi = [False] * (n + 1)12uyum = [(0, 1)]13while uyum:14  narx, u = heapq.heappop(uyum)15  if tugadi[u]:16      continue17  tugadi[u] = True18  for v, w in qoshni[u]:19      if narx + w < masofa[v]:20          masofa[v] = narx + w21          heapq.heappush(uyum, (masofa[v], v))22print(masofa[1:])

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1import heapq2n = 53qirralar = [(1, 2, 4), (1, 3, 2), (2, 3, 1), (2, 4, 5), (3, 4, 8), (4, 5, 3)]4qoshni = [[] for _ in range(n + 1)]5for a, b, w in qirralar:6  qoshni[a].append((b, w))7  qoshni[b].append((a, w))8CHEKSIZ = float("inf")9masofa = [CHEKSIZ] * (n + 1)10masofa[1] = 011tugadi = [False] * (n + 1)12uyum = [(0, 1)]13while uyum:14  narx, u = heapq.heappop(uyum)15  if tugadi[u]:16      continue17  tugadi[u] = True18  for v, w in qoshni[u]:19      if narx + w < masofa[v]:20          masofa[v] = narx + w21          heapq.heappush(uyum, (masofa[v], v))22print(masofa[1:])

Sizning bashoratingizTekshirish

Javobni ko'rish

[0, 3, 2, 8, 11]

Javob bir xil. if tugadi[u]: continue qatori muhim: uyumga bir uch bir necha marta tushishi mumkin, lekin u faqat bir marta ishlanadi.

◆Asosiy g'oya

Uyumdan chiqqan uchning narxi yakuniy bo’ladi. Nega: narxlar musbat, demak boshqa har qanday yo’l allaqachon shundan qimmat bo’lgan uchdan o’tadi va qo’shimcha qirra narxni faqat oshiradi.

Va nega manfiy vaznda buziladi

Yuqoridagi mulohaza «narxlar musbat» degan shartga tayanadi. Uni olib tashlasak, u bilan birga kafolat ham yo’qoladi — buni ko’rish uchun to’rt uchli grafcha yetadi.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1import heapq2qoshni = {1: [(2, 5), (3, 6)], 2: [(4, 1)], 3: [(2, -4)], 4: []}3CHEKSIZ = float("inf")4masofa = {u: CHEKSIZ for u in qoshni}5masofa[1] = 06tugadi = set()7uyum = [(0, 1)]8while uyum:9  narx, u = heapq.heappop(uyum)10  if u in tugadi:11      continue12  tugadi.add(u)13  for v, w in qoshni[u]:14      if narx + w < masofa[v]:15          masofa[v] = narx + w16          heapq.heappush(uyum, (masofa[v], v))17print(masofa[4])

Sizning bashoratingizTekshirish

Javobni ko'rish

6

Haqiqiy javob 3: yo'l 1 → 3 → 2 → 4 narxi 6 − 4 + 1 = 3. Dijkstra esa 2-uchni 5 narxda YAKUNLAB qo'ydi va o'sha 5 dan foydalanib 4-uchga 6 yozdi. Keyin 2 arzonlashdi, lekin 4 allaqachon hisoblab bo'lingan edi.

Manfiy vazn bo’lganda sekin.py dagi usul ishlatiladi — u tartib tanlamagani uchun hech narsani muddatidan oldin yakunlamaydi.

Sinab ko’r

Vizualda uch ustidagi son — hozirgi eng yaxshi narx. Uch to’q rangga o’tsa, uning narxi qotdi.

Dijkstra — eng arzon yo'l

Uch ustidagi son — hozirgi eng yaxshi narx. Uch to'q rangga o'tsa, narxi qotdi.

Har qadamda eng arzon tugallanmagan uch olinadi va uning qo'shnilari narxi yangilanadi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Qirralardagi sonlar — narx. 1-uchdan boshlaymiz, uning narxi 0. BFS bu yerda ishlamaydi: kam qirrali yo'l qimmatroq bo'lishi mumkin.
2. Uyumdagi eng arzoni — 1 uchi, narxi 0. Bu son endi YAKUNIY: narxlar musbat, demak boshqa yo'l bilan arzonroq kelib bo'lmaydi.
3. 1 orqali yangi narxlar: 2: yo‘q edi -> 4; 3: yo‘q edi -> 2.
4. Uyumdagi eng arzoni — 3 uchi, narxi 2. Bu son endi YAKUNIY: narxlar musbat, demak boshqa yo'l bilan arzonroq kelib bo'lmaydi.
5. 3 orqali yangi narxlar: 2: 4 -> 3; 4: yo‘q edi -> 10.
6. Uyumdagi eng arzoni — 2 uchi, narxi 3. Bu son endi YAKUNIY: narxlar musbat, demak boshqa yo'l bilan arzonroq kelib bo'lmaydi.
7. 2 orqali yangi narxlar: 4: 10 -> 8.
8. Uyumdagi eng arzoni — 4 uchi, narxi 8. Bu son endi YAKUNIY: narxlar musbat, demak boshqa yo'l bilan arzonroq kelib bo'lmaydi.
9. 4 orqali yangi narxlar: 5: yo‘q edi -> 11.
10. Uyumdagi eng arzoni — 5 uchi, narxi 11. Bu son endi YAKUNIY: narxlar musbat, demak boshqa yo'l bilan arzonroq kelib bo'lmaydi.
11. Tayyor. Har uch ustidagi son — 1-uchdan eng arzon yo'l narxi. MANFIY narx bo'lganda bu usul buziladi: keyin kelgan qirra narxni kamaytirishi mumkin.

Qirralardagi sonlar — narx. 1-uchdan boshlaymiz, uning narxi 0. BFS bu yerda ishlamaydi: kam qirrali yo'l qimmatroq bo'lishi mumkin.

Yakunlangan uch0

OrqagaO‘ynatishOldinga1/11Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

24 / 40

MasalaVaznli grafda 1-uchdan eng arzon narxlarni toping.

Taklif qilingan yechim

1. 1Uyumga (0, 1) ni solamiz.
2. 2Uyumdan eng arzonini olamiz va uni tugadi deb belgilaymiz.
3. 3Uning har qo‘shnisi uchun narxni yangilaymiz va uyumga qo‘shamiz.
4. 4Uyum bo‘shaguncha davom etamiz.

Bu javobning 3-qismi noto'g'ri. Yangilash SHARTSIZ bajarilmoqda. Narx yaxshilanmagan bo'lsa ham uyumga yozuv qo'shilaveradi va uyum keraksiz o'sadi — zich grafda u m emas, m² yozuv saqlashi mumkin. To'g'risi: faqat narx + w < masofa[v] bo'lgandagina yangilash va qo'shish.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Nega vaznli grafda BFS ishlamaydi?

Javobni ko'rish

BFS qirralar sonini sanaydi, narxni emas. Ko’p qirrali yo’l arzonroq bo’lishi mumkin, BFS esa uni ko’rmaydi.

2Uyumdan chiqqan uchning narxi nega yakuniy?

Javobni ko'rish

Narxlar musbat. Boshqa har qanday yo’l allaqachon shundan qimmat bo’lgan uchdan o’tadi, qo’shimcha qirra esa narxni faqat oshiradi.

3Manfiy vaznda Dijkstra qanday adashadi?

Javobni ko'rish

U uchni erta yakunlaydi. Keyin arzonroq yo’l topilsa ham, o’sha uch orqali hisoblangan qo’shnilar qayta hisoblanmaydi va noto’g’ri qoladi.

4if tugadi[u]: continue qatori nima uchun kerak?

Javobni ko'rish

Uyumga bir uch bir necha marta tushishi mumkin — har yaxshilanishda yangi yozuv qo’shiladi. Eskirgan yozuvlar shu qator bilan tashlanadi.

5Manfiy vazn bo'lsa qaysi usul ishlatiladi?

Javobni ko'rish

Tartib tanlamaydigan, takror-takror yaxshilaydigan usul — darsdagi sekin.py. U hech narsani muddatidan oldin yakunlamaydi, shuning uchun manfiy vaznda ham to’g’ri.

Masalalar

Masalalar

3 ta

• Shortest Routes ICSES 1671o'rta

  Darsdagi masalaning o‘zi, bir tomonlama yo‘llar bilan.

• Flight DiscountCSES 1195qiyin

  Grafni ikki nusxaga ko‘paytiring: chegirma ishlatilgan va ishlatilmagan holatlar.

• High ScoreCSES 1673qiyin

  Vaznlar manfiy — Dijkstra yaramaydi. Cheksiz o‘sadigan halqani ham aniqlash kerak.

Lokal mashq: mashqlar/24-eng-arzon/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Beshta shaharli xarita chizing va narxlarni yozing. Dijkstra ni qo’lda bajaring: har qadamda qaysi shahar tanlanganini va nima yangilanganini yozib boring.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

24-eng-arzon masalasini yeching. Yechimingizni bog’lanmagan grafda ham sinang — yetib bo’lmaydigan uchlar uchun javob to’g’ri chiqdimi?

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Darsdagi manfiy vaznli grafni oling va sekin.py usulini unda yurgizing — u to’g’ri javob (3) beradimi? Keyin grafga manfiy halqa qo’shing va o’sha yechim bilan nima bo’lishini tushuntiring.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim