graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari

PPTX 10 стр. 295,3 КБ Бесплатная загрузка

10 стр.

FaylHub.uz

Скачать через Telegram

Размер 295,3 КБ

Тип файла PPTX

Страницы 10

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

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

Хотите читать дальше?

Скачайте все 10 страниц бесплатно через Telegram.

Скачать полный файл

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

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...

Этот файл содержит 10 стр. в формате PPTX (295,3 КБ). Чтобы скачать "graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari", нажмите кнопку Telegram слева.

Теги: graflarda eng qisqa yo'lni aniq… PPTX 10 стр. Бесплатная загрузка Telegram