|
Algoritmlarni loyihalash fanidan mustaqil ishi
|
| bet | 10/10 | | Sana | 27.05.2024 | | Hajmi | 0,61 Mb. | | #254553 |
Bog'liq algoritm.MIDEYKSTRA ALGORITMI
Berilgan tugundan (uni 0 deb bilgilaymiz) barcha boshqa tugunlarga bo’lgan qisqa masofalarni hisoblash uchun amalda qullaniladi. Algoritm samaradorligi amallar bajarilishi bo’yicha n2 tartibli hisoblanadi. Bu algoritmda qirralar o’girlik qiymatlari faqat musbat bo’lishi lozim.
Algoritm g’oyasi:
Qisqa masofani aniqlash uchun qaysi bir tugunlardan tashkil topilishi uchun qushimcha mantiqiy elementladan tashkil topgan mark[0 .. n–1] massiv kiritamiz. Uning elementlari qiymati true qiymatga teng bo’ladi, agar ushbu tugundan o’tilgan (belgilangan) bo’lsa, false qiymatga teng bo’ladi agar o’tilmagan (belgilanmagan) bo’lsa. d[0 .. n–1] masofalar massivi har i-chi qadamda javobini saqlash uchun ishlatiladi va har qadamda i-dan oshmagan qirallar 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 - 1
if (not mark[i]) and ((v == -1) or (d[v] > d[i]))
v = i
mark[v] = True
for i = 0 ... n - 1
if d[i] > d[v] + g[v][i]
d[i] = d[v] + g[v][i]
d massiv natijasini ekranga chiqarish
Xulosa
Xulosa o'rnida aytadigan bo'lsak, bu mustaqil ishni bajarish davomida graflar haqida umumiy tushunchalarimni yanada boyitib, yangi algoritmlar haqida kerakli ma’lumotlarni o’zim uchun kashf qildim va o’rganib oldim.
Graflarni eniga va boyiga tekshirishda yuqorida korsatilgan korish usullari anchagina foydali ekan. graflarni kundalik hayotda kop ishlatganimiz bois mustaqil ish qilish davomida organgan algoritmlarim bilan a manzildan b manzilga borishdagi eng qisqa yol yoki eng samarali va tejamkor yollarni topish uchun keng kolamda qollash mumkin ekan.
Foydalanilgan adabiyotlar:
O. R. Yusupov, I. Q. Ximmatov, E. Sh. Eshonqulov. Algoritmlar va berilganlar strukturalari. Oliy oʻquv yurtlari uchun oʻquv qoʻllanma. – Samarqand:
AdamDrozdek. 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
|
| |
