O`ZBEKISTON RESPUBLIKASI AXBOROT
TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH
VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI
UNIVERSITETI SAMARQAND FILIALI
“AXBOROT TA’LIM TEXNOLOGIYALARI”
KAFEDRASI
"Taqsimlangan aloritmlar va tizimlar"
fanidan
Bajardi: To’ychiboyev U.
Qabul qildi: Xusanov.K
SAMARQAND – 2023
Mavzu: Marshrutlash algoritmi. Hamma juftlilar uchun eng qisqa yo’l
masalasi. Floyd-Uorshell algoritmi.
Ishdan maqsad: Eng qisqa yo’lni mtopishni Floyd- Uorshell algoritmi
yordamida o’rganish va dasturiy ta’minot yaratish.
Nazariy qism.
Floyd-Uorshell algoritmi - bu og'irlikdagi yo'naltirilgan grafikning barcha
vertikalari orasida eng qisqa masofani topish uchun dinamik algoritmdir. Robert
Floyd va Stiven Uorshell 1962 yilda ishlab chiqilgan. Algoritm birinchi bo'lib
1959 yilda Bernard Roy tomonidan ishlab chiqilgan va nashr etilgan. Graf
cho’qqilari
𝐺 = (𝑉, 𝐸),|𝑉| = 𝑛1 dan n gacha raqamlanganva eng qisqa yo’lni i dan
j gacha topish uchun dk ij belgilash kiritilgan bo’lsin.Bunda i, j cho’qqilar faqat
1…k cho’qqilar orqali o’tadi. Bundan, 𝑑𝑖𝑗 0 − (𝑖,𝑗) qirraning uzunligi ekanligi
aniq bo’ladi, agar bunday yo’l mavjud bo’lsa (aks holda uning uzunligi ∞
ko’rinishida belgilanishi mumkin).
𝑑𝑖𝑗 𝑘 , 𝑘 ∈ (1, … , 𝑛)qiymati uchun
ikkita
variant mavjud:
1.
𝑖,𝑗orasidagi eng qisqa yo’l k orqali o’tadi, agar 𝑑𝑖𝑗
𝑘 = 𝑑𝑖𝑗 𝑘−1
bo’lganda.
2.
𝑖,𝑗orasida k orqali o’tadigan yanayam qisqa yo’l mavjud, agar u oldin i dan k
ga o’tib, keyin k dan j ga o’tsa. Bunday holda,
𝑑𝑖𝑗
𝑘 = 𝑑𝑖𝑘 𝑘−1 + 𝑑𝑘𝑗 𝑘−1 .
Shunday qilib, funktsiyaning qiymatini topish uchun ikki ko'rsatilgan
qiymatning minimumini tanlash kifoya. Shunda
𝑑𝑖𝑗 𝑘
uchun davriy funksiya
quyidagi ko’rinishga ega bo’ladi:
𝑑𝑖𝑗 0 − (𝑖,𝑗)qirra uzunligi. 𝑑𝑖𝑗 𝑘 = min (𝑑𝑖𝑘 𝑘−1
+
𝑑𝑘𝑗 𝑘−1).
Floyd-Uorshell algoritmi ketma-ketlik bilan ixtiyoriy i,j va d (1
dan n
gacha) uchun
𝑑𝑖𝑗 𝑘 ning barcha qiymatlarini hisblaydi. Olingan 𝑑𝑖𝑗 𝑛 qiymat 𝑖,𝑗
qirralar orasidagi kritik yo’lning uzunligi hisoblanadi.
Algoritmni amalga oshirilishida bitli maskalardan foydalanish algoritmni
ishlashini sezilarli tezlashtiradi. Bunda algoritmning murakkabligi
𝑂(𝑛 3 /𝑘) gacha
pasayadi, bunda k – bitli maskaning uzunligi (RAM hisoblash modelida).
1-rasm
Dastur natijasi :
2-rasm
Xulosa
Ushbu laboratoriya ishi orqali men bu algoritim
qanday ishlashi haqida
birqancha ma’lumotlarga ega bo’lib oldim . Menga ushbu laboratoriya ishini
bajarish maroqli va albatta qiziqarli bo’ldi hammasi juda ajoyib va samarali tarzda
amalga oshdi dastur kodi ishladi unda kamchiliklar topilmadi .