graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari

PPTX 10 pages 295.3 KB Free download

10 pages

FaylHub.uz

Download via Telegram

Size 295.3 KB

File type PPTX

Pages 10

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

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

Want to read more?

Download all 10 pages for free via Telegram.

Download full file

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

This file contains 10 pages in PPTX format (295.3 KB). To download "graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari", click the Telegram button on the left.

Tags: graflarda eng qisqa yo'lni aniq… PPTX 10 pages Free download Telegram