O`zbekiston respublikasi raqamli texnologiyalar vazirligi

O`ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI


MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI
UNIVERSITETI SAMARQAND FILIALI

"Kompyuter injiniring" fakulteti

"Kompyuter tizimlari" kafedrasi
"Taqsimlangan Algoritmlar va Tizimlar" fanidan

LABORATORIYA ISH_3

Mavzu: Marshrutlash algoritmi. Hamma juftlilar uchun eng qisqa yo’l

masalasi. Floyd-Uorshell algoritmi.
Bajardi: Isomiddinov S.
Tekshirdi: 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:

def floyd_warshall(graph):
n = len(graph)
dist = [[graph[i][j] for j in range(n)] for i in range(n)]
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
#
# Example usage
G = [[0,float('inf'),6,122,25],
[34,0,float('inf'),float('inf'),37],
[7,23,0,float('inf'),float('inf')],
[float('inf'),29,float('inf'),0,float('inf')],
[float('inf'),float('inf'),11,float('inf'),0]]

dist = floyd_warshall(G)

for row in dist:
print(row)

Dastur natijasi


Xulosa
Men ushbu laboratoriyani matritsa tuzib bajardim . . Graflar haqida ma’lumot oldim. U qanday ishlashini amaliyotda ko’rdim.