Zbekiston respublikasi axborot texnologiyalari va

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).
 

 
 
Topshiriq: 
Floyd-Uorshel lalgoritmidan foydalanib berilgan grafdagi eng qisqa yo’lni 
topish dasturiy ta’minotini tuzing. 
Dastur kodi: 

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 .