Tekshirdi: Begimov O’ktam Toshkent 2023 Mavzu: Prima Deykstra algoritmi. Uni vaqt bo'yicha baholasho. Reja

Algaritmi
Barcha tugunlarni ko'rilmagan deb belgilang. Ko'rilmagan to'plam deb ataladigan barcha ko'rilmagan tugunlar to'plamini yarating.
Har bir tugunga taxminiy masofa qiymatini belgilang: uni boshlang'ich tugunimiz uchun nolga, qolgan barcha tugunlar uchun cheksizga qo'ying. Algoritmni ishga tushirish vaqtida v tugunining taxminiy masofasi v tugun va boshlang'ich tugun o'rtasida aniqlangan eng qisqa yo'lning uzunligidir. Dastlab manbaning o'zidan boshqa cho'qqilarga hech qanday yo'l ma'lum bo'lmagani uchun (bu nol uzunlikdagi yo'l), boshqa barcha taxminiy masofalar dastlab cheksizlikka o'rnatiladi. Dastlabki tugunni joriy sifatida o'rnating.
Joriy tugun uchun uning barcha ko'rilmagan qo'shnilarini ko'rib chiqing va joriy tugun orqali ularning taxminiy masofalarini hisoblang. Yangi hisoblangan taxminiy masofani hozirda qo'shniga tayinlangan masofa bilan solishtiring va uni kichikroq qilib belgilang. Misol uchun, agar joriy tugun A 6 masofa bilan belgilangan bo'lsa va uni qo'shni B bilan bog'laydigan chekka 2 uzunlikka ega bo'lsa, u holda A orqali B gacha bo'lgan masofa 6 + 2 = 8 bo'ladi. Agar B ilgari bilan belgilangan bo'lsa. masofa 8 dan katta bo'lsa, uni 8 ga o'zgartiring. Aks holda, joriy qiymat saqlanadi.
Joriy tugunning barcha ko'rilmagan qo'shnilarini ko'rib chiqishni tugatgandan so'ng, joriy tugunni tashrif buyurilgan deb belgilang va uni ko'rilmagan to'plamdan olib tashlang. Tashrif buyurilgan tugun boshqa hech qachon tekshirilmaydi (bu 6-bosqichdagi xatti-harakatlar bilan bog'liq holda to'g'ri va maqbuldir: keyingi tashrif buyuriladigan tugunlar har doim "birinchi tugundan eng kichik masofa" tartibida bo'ladi, shuning uchun keyingi tashriflar kattaroq masofaga ega).
Belgilangan tugun tashrif buyurilgan bo'lsa (ikkita aniq tugunlar orasidagi marshrutni rejalashtirishda) yoki ko'rilmagan to'plamdagi tugunlar orasidagi eng kichik taxminiy masofa cheksizlik bo'lsa (to'liq o'tishni rejalashtirganda; boshlang'ich tugun o'rtasida aloqa bo'lmaganda sodir bo'ladi) va qolgan ko'rilmagan tugunlar), keyin to'xtating. Algoritm tugadi.
Aks holda, eng kichik taxminiy masofa bilan belgilangan tashrif buyurilmagan tugunni tanlang, uni yangi joriy tugun sifatida o'rnating va 3-bosqichga qayting.
Marshrutni rejalashtirayotganda, yuqoridagidek, maqsad tuguniga “tashrif buyurilishini” kutishning hojati yo‘q: maqsad tugun barcha “tashrif buyurilmagan” tugunlar orasida eng kichik taxminiy masofaga ega bo‘lgandan keyin algoritm to‘xtashi mumkin (shuning uchun “tashrif buyurilgan” tugun sifatida tanlanishi mumkin). keyingi "joriy").