graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari

PPTX 10 sahifa 295,3 KB Bepul yuklash

10 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 295,3 KB

Fayl turi PPTX

Sahifalar 10

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 10

prezentatsiya powerpoint graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari guruh: swd025 bajardi: yaxshiliqov sh tekshirdi: ganixodjaeva d mustaqil ish tatu toshkent2022 ma’lumotlar tuzilmasi va algoritmlar 1 reja: graflarda eng qisqa yo’lni aniqlash haqida graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili deykstra algoritmi 2 graflarda eng qisqa yo’lni aniqlash haqida graflar nazariysida eng qisqa yo’lni aniqlash muhim klassik masalalaridan biri deb hisoblanadi. uni hisoblash va echimlarni topish uchun bir qancha algoritmlari mavjud. eng qisqa yo’l masalasi (inglizchada – shortest path problem) – bu grafning ikkita tugun orasidagi eng qichik yo’l (masofa, zanjir, marshrut) topish masalasidir, qaysidaki yoylarning vaznilarining yig’indisi minimal qiymatga ega. qisqa (oddiy) zanjir geodezik zanjir ham aytiladi. ushbu masalani adabiyotlarda bir nechta boshqa nomlanishi ham uchratish mumkin: minimal masofa masalasi, dilijans masalasi, qisqa masofa masalasi va boshqalar. grafda eng qisqa masofani topish masalasi yo’naltirilgan, yo’naltirilmagan va aralash graflarda echimini aniqlash mumkin masalani formal quyilishi: g = (v, e). yuklanishga …

2 / 10

agi qisqa masofani aniqlash masalasi (all-pairs shortest path problem). xar bir u tugundan xar bir v tugungacha qisqaroq yo’lni aniqlash masalasi eng qisqa yo'lni aniqlash masalasi har hil masalalarda berilishiga qarab quyidagicha talafuzlarga ega bo’lish mumkin. 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 …

3 / 10

r 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. algoritmning psevdokodi: g grafni o’qib olamiz // g[0 ... n - 1][0 ... n - 1] - qirallar og’irliklari matritsasi, g[i][j] = 2000000000, agar i va j tugunlar orasida qirra mavjud bo’lmasa d[0] = 0 //0 -tanlangan tugun d = g[0] mark[0] = true for i = 1 .. n - 1 mark[i] = false for i = 1 .. n - 1 v = -1 for i = 0 .. n …

4 / 10

graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari - Page 4

5 / 10

graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari - Page 5

Ko'proq o'qimoqchimisiz?

Barcha 10 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari" haqida

prezentatsiya powerpoint graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari guruh: swd025 bajardi: yaxshiliqov sh tekshirdi: ganixodjaeva d mustaqil ish tatu toshkent2022 ma’lumotlar tuzilmasi va algoritmlar 1 reja: graflarda eng qisqa yo’lni aniqlash haqida graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili deykstra algoritmi 2 graflarda eng qisqa yo’lni aniqlash haqida graflar nazariysida eng qisqa yo’lni aniqlash muhim klassik masalalaridan biri deb hisoblanadi. uni hisoblash va echimlarni topish uchun bir qancha algoritmlari mavjud. eng qisqa yo’l masalasi (inglizchada – shortest path problem) – bu grafning ikkita tugun orasidagi eng qichik yo’l (masofa, zanjir, marshrut) topish masalasidir, qaysidaki yoylarning vaznilarining yig’indisi minimal qiymatga ega. qisqa (oddi...

Bu fayl PPTX formatida 10 sahifadan iborat (295,3 KB). "graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: graflarda eng qisqa yo'lni aniq… PPTX 10 sahifa Bepul yuklash Telegram