Internet va axborot kommunikatsiyasi fakulteti

1-misol. Grafikdagi eng qisqa yo'lni tepadan toping L tepaga D(10.7-rasm).
Guruch. 10.7.
Algoritmni bosqichlar ketma-ketligi shaklida yozamiz (10.1-jadval). Qadam 1. Boshlang'ich cho'qqigacha bo'lgan masofani aniqlang L hammadan oldin.
10.1-jadval
Dijkstra usuli (birinchi qadam)

Qadam 2. dan eng kichik masofani tanlang L oldin V; cho'qqisi topildi V yangi tanlangan sifatida qabul qilinadi. Topilgan eng kichik masofa yangi tepadan qirralarning uzunliklariga qo'shiladi V hammadan oldin. Biz minimal masofani tanlaymiz V oldin N. Yangi cho'qqi N biz tanlanganni olamiz (10.2-jadval).
10.2-jadval
Deykstra usuli (ikkinchi bosqich)

Aniqlik uchun, keyingi gaplarda oo belgisi o'rniga "-" belgisini qo'yamiz.
Qadam 3. Yuqoridan masofani aniqlang N l qolganlari haqida (shundan tashqari L va V), jadvalda ko'rsatilganidek. 10.3.
10.3-jadval
Dijkstra usuli (uchinchi bosqich)

Tepadan masofa L tepa bo'ylab N uchun tepalar G 18 ta shartli birlikka teng. Bu masofa masofadan kattaroqdir LB + BG= 16 an'anaviy birlik, buning natijasida kelajakda hisobga olinmaydi. Shunga o'xshash konstruktsiyalarni davom ettirib, biz jadval tuzamiz. 10.4. Shunday qilib, cho'qqilar orasidagi eng qisqa yo'lning uzunligi topildi L va D(44 an'anaviy birlik).
Yo'lning traektoriyasi quyidagicha aniqlanadi. Biz oxirgi cho'qqidan boshlang'ich nuqtaga teskari qidiruvni amalga oshiramiz. Biz yuqoridan yuqoriga mos keladigan ustunni ko'rib chiqamiz va minimal qiymatning birinchi paydo bo'lishini aniqlaymiz. Tepaga mos keladigan ustunda D, birinchi marta to'rtinchi qatorda pastki qismida 44 ta an'anaviy birlikning minimal uzunligi paydo bo'ldi. Bu chiziq cho'qqini ko'rsatadi S, qaysi biri borishi kerak, ya'ni. keyin biz tepaga mos keladigan ustunni ko'rib chiqishimiz kerak S.
10.4-jadval

Ushbu ustunda minimal uzunligi 27 an'anaviy birlik keyingi cho'qqini ko'rsatadi G, qaysi biri borishi kerak va hokazo. Shunday qilib, biz yo'lning traektoriyasini olamiz: (L, B, G, S, D).
8-misol. Grafikda 1 va 7 cho'qqilar orasidagi eng qisqa yo'lni toping (10.8-rasm).
Keyingi tanlangan cho'qqini aniqlang (10.5-jadval) masofasi eng kichik bo'lgan va tanlanmaganlar to'plamiga tegishli cho'qqilardan biriga chekka bilan bog'langan (bu masofa tanlangan cho'qqigacha bo'lgan masofaga va uzunligiga teng bo'ladi) chetidan).



Guruch. 10.8. Grafik (a) va mos keladigan qo'shnilik matritsasi (b)
Deykstra usulini jadval shaklida amalga oshirish
1 0.5-jadval

Biz oxirgi cho'qqidan boshlang'ich nuqtaga teskari qidiruvni amalga oshiramiz.

Biz yuqoridan yuqoriga mos keladigan ustunni ko'rib chiqamiz va minimal qiymatning birinchi paydo bo'lishini aniqlaymiz. Bu holda eng qisqa yo'l teng bo'ladi (V 7 - V 5 - V 2 - Y ().
va NAZORAT SAVOLLARI

• 
  1. Algoritmlarning nazariy murakkabligi nimada: qarorlar daraxtini qurish, dinamik dasturlash va Dijkstra?
  
• 
  2. Yo'naltirilgan va yo'naltirilmagan grafiklar uchun qarorlar daraxtidan foydalanishning o'ziga xos xususiyati nimada?
  
• 
  3. Grafikda berilgan cho’qqilar orasidagi eng qisqa masofalarni aniqlash algoritmlari qanday amaliy masalalarni yechishda qo’llaniladi?
  
• 
  4. Ishda ko'rib chiqilgan Deykstra algoritmini yo'naltirilgan grafikdagi eng qisqa masofani aniqlashda qo'llash mumkinmi?
  
• 
  5. Deykstra algoritmi qanday ishlaydi?
  
• 
  6. Grafikdagi cho’qqilar orasidagi eng qisqa masofalarni aniqlash masalasiga nisbatan dinamik dasturlash algoritmi qanday ishlaydi?
  

Dijkstra algoritmi - manfiy bo'lmagan yoy uzunliklariga ega bo'lgan grafikdagi ikkita berilgan cho'qqilar orasidagi eng qisqa yo'lni topadigan grafik algoritmi. Bundan tashqari, ko'pincha berilgan cho'qqidan qolgan barcha nuqtalarga eng qisqa yo'lni hisoblash vazifasi qo'yiladi. Algoritm dasturlashda keng qo'llaniladi, masalan, marshrutlash protokollari tomonidan qo'llaniladi.
Tavsif
Algoritmning kiritilishi manfiy bo'lmagan og'irlikdagi yoylarga ega bo'lgan vaznli yo'naltirilgan grafikdir. Chiqish bu cho'qqidan boshqalarga eng qisqa yo'llar to'plamidir.
Dastlab, boshlang'ich cho'qqi uchun masofa nolga teng, qolganlarigacha bo'lgan masofalar esa cheksiz deb qabul qilinadi. Cho'qqidan o'tganligini ko'rsatadigan bayroqlar massivi nol bilan to'ldirilgan. Keyin, tsiklning har bir bosqichida boshlang'ichgacha minimal masofa va nolga teng bayroq bilan cho'qqi qidiriladi. Buning uchun bayroq o'rnatiladi va barcha qo'shni cho'qqilar tekshiriladi. Agar dastlabki cho'qqidan tekshirilgan cho'qqigacha bo'lgan oldindan hisoblangan masofa joriy cho'qqigacha bo'lgan masofa va undan belgilangan cho'qqigacha bo'lgan chekka uzunligi yig'indisidan katta bo'lsa, u holda tekshirilgan cho'qqigacha bo'lgan masofa masofaga tenglashtiriladi. joriy + chekka oqimdan tekshirilgan cho'qqigacha. Barcha cho'qqilarning bayroqlari 1 ga teng bo'lganda yoki bayroq 0 bo'lgan barcha cho'qqilarga masofa cheksiz bo'lganda tsikl tugaydi. Oxirgi holat, agar grafik uzilgan bo'lsa, mumkin.