Graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari guruh: swd025 bajardi: yaxshiliqov sh tekshirdi: ganixodjaeva d

Graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili Hozirgi kunga kelib graflarda eng qisqa y’olni aniqlash uchun ko’plab algoritmlar ishlab chiqilgan. Ularni amalga oshirish masalaning berilishiga qarab foydalanish mumkin. Hayotiy masalalarida odatda vaznga ega bo’lgan graf tuzilmalarida eng qisqa yo’lni aniqlash algoritmlari qullaniladi. Graflarda eng qisqa yo‘lni aniqlash algoritmlari Vaznga ega bo’lgan graf tuzilmasini kompyuter hotirasiga saqlash uchun quyidagi belgilanishlarini aytib o’tamiz: n – tugunlar soni; m – qirralar soni; g[n][n] – grafning qo’shma matritsasi; g[n][m] – grafning intsidientlik matritsasi; e[m] – grafning qirralar ro’yhati (uchta maydondan iborat (boshlangich va yakunlovchi tugunlar raqami va qirraning og’irlik qiymati)); w[i][j] – qirraning og’irligi (vazni, o’lchami) matritsasi; d – masofa birligi; d[n] – berilgan tugundan boshqa tugunlarga qisqa masofalar massivi; d[n][n] – tugundan boshqa tugunlarga masofalar matritsasi.
DEYKSTRA ALGORITMI Berilgan tugundan (uni 0 deb bilgilaymiz) barcha boshqa tugunlarga bo’lgan qisqa masofalarni hisoblash uchun amalda qullaniladi. Algoritm samaradorligi amallar bajarilishi bo’yicha n2 tartibli hisoblanadi. Bu algoritmda qirralar o’girlik qiymatlari faqat musbat bo’lishi lozim. Algoritm g’oyasi: Qisqa masofani aniqlash uchun qaysi bir tugunlardan tashkil topilishi uchun qushimcha mantiqiy elementladan tashkil topgan mark[0 .. n–1] massiv kiritamiz. Uning elementlari qiymati true qiymatga teng bo’ladi, agar ushbu tugundan o’tilgan (belgilangan) bo’lsa, false qiymatga teng bo’ladi agar o’tilmagan (belgilanmagan) bo’lsa. d[0 .. n–1] masofalar massivi har i-chi qadamda javobini saqlash uchun ishlatiladi va har qadamda i-dan oshmagan qirallar soni ishtirokida masofa hisoblash uchun foydalaniladi. Boshlangich qadamda 0 tuguni belgilanadi, d[i]=x(qirra og’irligiga), agar 0 va i tugunlar orasida qirra mavjud bo’lsa. d[i]= 2000000000 (cheksiz qiymatga), agar qirra 0 va i tugunlar o’rtasida bo’lmasa. Xar keyingi qadamda belgilanmagan tugunlar o’rtasidan eng minimal qiymatga ega bo’lgan tugun tanlanadi uni v deb belgilaymiz. U holda d[v] v tugun uchun javobi deb hisoblanadi. Keyin v-tugunni belgilab olamiz va d qiymatlarini qayta hisoblab chiqamiz. Bu amallarni barcha tugunlar belgilanmaguncha davom etiramiz.