graflarda eng qisqa yo‘lni aniqlash haqida

PPTX 14 pages 385.0 KB Free download

14 pages

FaylHub.uz

Download via Telegram

Size 385.0 KB

File type PPTX

Pages 14

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

1 / 14

graflarda eng qisqa yo‘lni aniqlash algoritmlari. lug‘atlar va ularni amalga oshirish. graflarda eng qisqa yo‘lni aniqlash algoritmlari. lug‘atlar va ularni amalga oshirish. guruh: swd002 talaba: shamshiddinov abdumo`min tekshirdi: isxakova nargiza reja: 1. graflarda eng qisqa yo’lni aniqlash haqida 2.graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili 3. floyd – uorshell algoritmi 4. ford – belmann algoritmi 5. deykstra algoritmi 1. graflarda eng qisqa yo’lni aniqlash haqida graflar nazariysida eng qisqa yo’lni aniqlash muhim klassik masalalaridan biri deb hisoblanadi. uni hisoblash va yechimlarni 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 vaznlarining 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 …

2 / 14

d tugungacha bo'lgan eng qisqa yo'lni aniqlash talab etiladi. berilgan tugundan barcha tugunlarga bo'lgan qisqa yo'llarni aniqlash masalasi (single-source shortest path problem). berilgan punktga yetib borishning qisqaroq yo'lini aniqlash masalasi (single-destination shortest path problem). grafning barcha tugunlaridan v tugunga yetib borishning qisqaroq yo'lini aniqlash talab etiladi. barcha o'zaro tugunlar orasidagi qisqa masofani aniqlash masalasi (all-pairs shortest path problem). xar bir u tugundan xar bir v tugungacha qisqaroq yo'lni aniqlash masalasi. har qanday masalalar berilishida yoyning og’irligi nafaqat uzunligi kabi aniqlanadi, ammo uning o’tish vaqti, harajati, narxi, resurslarning sarf hajmi va boshqa hussusiyatlar orqali aniqlanishi mumkin. shu sababli ushbu masala ko’plab sohalarda (informatika, iqtisodiyot, geografiya va boshqalar) amaliy qo’lanilish masalalari va yechimlariga ega. 2.1. floyd – uorshell algoritmi har qanday tugunlardan barcha tugunlarga bo’lgan masofalarni hisoblash uchun amalda qo`llaniladi. algoritm samaradorligi amallar bajarilishi bo’yicha n3 tartibli hisoblanadi. qirralar o’girlik qiymatlari manfiy ham bo’lishi mumkin, ammo manfiy qiymatga ega bo’lgan qirralar halqa …

3 / 14

- 1] - qirralar og’irliklari matritsasi, g[i][j] = 2000000000, agar i va j tugunlar orasida qirra mavjud bo’lmasa d = g for i = 1 ... n + 1 for j = 0 ... n - 1 for k = 0 ... n - 1 if d[j][k] > d[j][i - 1] + d[i - 1][k] d[j][k] = d[j][i - 1] + d[i - 1][k] d matritsa natijasini ekranga chiqarish algoritmning dastur kodi: #include #include int main(){ int n, a[101][101]; ifstream ifs ("input.txt"); ifs>> n; for(int i=1; i > a[i][j]; ifs.close(); for(int k=1;k d[e[j].first] + e[j].value d[e[j].second] = d[e[j].first] + e[j].value if d[e[j].first] > d[e[j].second] + e[j].value d[e[j].first] = d[e[j].second] + e[j].value d massiv natijasini ekranga chiqarish ford-uorshell algoritmiga natija olish qadamlari algoritmning dastur kodi: #include #include int main(){ int n, a[101][101]; ifstream ifs ("input.txt"); ifs>> n; for(int i=1; i > a[i][j]; ifs.close(); for(int k=1; k d[i])) v = i mark[v] …

4 / 14

f ed he if iteration 234 ssssssoss © 10 10 10 ° 2 15 15 15 15 n /docprops/thumbnail.jpeg

5 / 14

graflarda eng qisqa yo‘lni aniqlash haqida - Page 5

Want to read more?

Download all 14 pages for free via Telegram.

Download full file

About "graflarda eng qisqa yo‘lni aniqlash haqida"

graflarda eng qisqa yo‘lni aniqlash algoritmlari. lug‘atlar va ularni amalga oshirish. graflarda eng qisqa yo‘lni aniqlash algoritmlari. lug‘atlar va ularni amalga oshirish. guruh: swd002 talaba: shamshiddinov abdumo`min tekshirdi: isxakova nargiza reja: 1. graflarda eng qisqa yo’lni aniqlash haqida 2.graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili 3. floyd – uorshell algoritmi 4. ford – belmann algoritmi 5. deykstra algoritmi 1. graflarda eng qisqa yo’lni aniqlash haqida graflar nazariysida eng qisqa yo’lni aniqlash muhim klassik masalalaridan biri deb hisoblanadi. uni hisoblash va yechimlarni 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) top...

This file contains 14 pages in PPTX format (385.0 KB). To download "graflarda eng qisqa yo‘lni aniqlash haqida", click the Telegram button on the left.

Tags: graflarda eng qisqa yo‘lni aniq… PPTX 14 pages Free download Telegram