ma’lumotlar tuzilmasi va algoritm

PPTX 29 pages 6.1 MB Free download

29 pages

FaylHub.uz

Download via Telegram

Size 6.1 MB

File type PPTX

Pages 29

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

1 / 29

graflarda eng qisqa yo‘lni aniqlash algoritmlari breadth first search bfs eniga qarab qidirish algortimi o’zbekiston respublikasi o’liy ta’lim , fan va innovatsiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalar universiteti ma’lumotlar tuzilmasi va algoritm 1-amaliy ish topshirig’i guruhi: swd018 bajardi : odilov ozodbek tekshirdi : isxakova (siddiqova) nargiza graflarda eng qisqa yo‘lni aniqlash algoritmlari breadth first search bfs eniga qarab qidirish algortimi graflarda eng qisqa yo‘lni aniqlash algoritmlari. reja: 1.graflarda eng qisqa yo’lni aniqlash haqida 2.graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili 2.1. floyd – uorshell algoritmi 2.2. ford – belmann algoritmi 2.3. deykstra algoritmi 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. data structures and algorithm eng qisqa yo’l masalasi (inglizchada – shortest path problem) – bu grafning ikkita tugun orasidagi eng qichik yo’l (masofa, zanjir, marshrut) topish masalasidir, …

2 / 29

ig'indisiga teng: berilgan grafda eng qisqa masofani topish masalasining formal qo’yilishi eng qisqa masofa aniqlash usullari eng qisqa yo'lni aniqlash masalasi har hil masalalarda berilishiga qarab quyidagicha talafuzlarga ega bo’lish mumkin: ikkita tugun orasidag eng qisqa masofani aniqlash masalasi (single-pair shortest path problem). s tugundan d tugungacha bo’lgan eng qisqa yo’lni aniqlash talab etiladi. berilgan tugundan barcha tugunlarga bo’lgan qisqa yo’llarni aniqlash masalasi berilgan punktga yetib borishning qisqaroq yo’lini aniqlash masalasi (single-source shortest path problem). (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 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 …

3 / 29

ishi bo’yicha n3 tartibli hisoblanadi. qirralar o’girlik qiymatlari manfiy ham bo’lishi mumkin, ammo manfiy qiymatga ega bo’lgan qirrallar halqa ko’rinishida berilmagan bo’lishi lozim, chunki algoritm sikllanib qolishi mumkin. algoritm g’oyasi: d[0 .. n–1][0 .. n–1] masofalar matritsasi har i-chi qadamda javobini saqlash uchun ishlatiladi va har keyingi qadamda i–1-dan kichik bo’lgan tugunlarga o’tish orqali kerakli masofani hisoblaydi. masalan, biz i-chi qadamni amalga oshirayapmiz. i+1 tugungacha masofalarni yangilash uchun i–1 tugun masofasini tanlaymiz va masofalarni shart orqali tekshiramiz. agar masofa kichikroq bo’lsa u holda masofa qiymatini yangilaymiz. va barcha qadamalr soni n+1 qiymatga teng. va oxirgi qadamdan so’ng bizlarda bir tugundan boshqa tugunlarga qisqa masofalar qiymati aniqlanadi va u d matritsasida saqlanadi. algoritm 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 = g for i = 1 …

4 / 29

$************* int a[500][500],d[500]={0}, n,s,f,flag[500],l,min1=100000000,nmin=0; for(inti=0;i > n >> s >> f; for(inti=1;i > a[i][j]; if(a[i][j]==-1&&i!=j) a[i][j]=32000; } ifs.close(); l=s; for(inti=1;i d[j]) { min1=d[j]; nmin=j; } l=nmin; flag[l]=0; for(int j=1;j<=n;j++) if(flag[j]!=0) d[j]=min(d[j],a[l][j]+d[l]); } ofstream ofs("output.txt"); if(d[f]==32000) ofs<<"-1"; else ofs<< d[f]; ofs.close(); return 0; } algoritmning dastur kodi: foydalanilgan adabiyotlar adabiyotlar. data structure and algorithms in c++. fourthedition. 2013. chapter 8. 391-490 betlar. a computer science portal for geeks. http://www.geeksforgeeks.org/data-structures/#graph http://www.tutorialspoint.com/data_structures_algorithms/graph_data_structure.htm image1.png image2.jpg image3.png image4.png image5.png image6.png image7.png image8.png image9.png image10.png 41 @ the onder of edges: ab bee eg ch dade di ef hg if iteration init 2 3 bos © 0 4 #10 coe 5 fo 293 s = 10 bod i 22 10 o © 10 10 10 ° 2 15 15 15 15 n$

5 / 29

ma’lumotlar tuzilmasi va algoritm - Page 5

Want to read more?

Download all 29 pages for free via Telegram.

Download full file

About "ma’lumotlar tuzilmasi va algoritm"

graflarda eng qisqa yo‘lni aniqlash algoritmlari breadth first search bfs eniga qarab qidirish algortimi o’zbekiston respublikasi o’liy ta’lim , fan va innovatsiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalar universiteti ma’lumotlar tuzilmasi va algoritm 1-amaliy ish topshirig’i guruhi: swd018 bajardi : odilov ozodbek tekshirdi : isxakova (siddiqova) nargiza graflarda eng qisqa yo‘lni aniqlash algoritmlari breadth first search bfs eniga qarab qidirish algortimi graflarda eng qisqa yo‘lni aniqlash algoritmlari. reja: 1.graflarda eng qisqa yo’lni aniqlash haqida 2.graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili 2.1. floyd – uorshell algoritmi 2.2. ford – belmann algoritmi 2.3. deykstra algoritmi graflarda eng qisqa yo’lni aniqlash haqida graflar nazariy...

This file contains 29 pages in PPTX format (6.1 MB). To download "ma’lumotlar tuzilmasi va algoritm", click the Telegram button on the left.

Tags: ma’lumotlar tuzilmasi va algori… PPTX 29 pages Free download Telegram