|
Va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiya universitut
|
| bet | 3/3 | | Sana | 20.11.2022 | | Hajmi | 97.65 Kb. | | #31013 |
Bog'liq Ma\'lumotlar tuzilmasi Informatika 00f9987, 2-sem maruza (7), elektrod potensial, Informatika va AT 2-dars, 01 O`zbekistonda inson huquqlari va erkinliklari kafolatinin 6 бет, 4-sinf texnologiya darsining 1 ta mavzusiga krassvord tuzish, Belbog’li kurash va Milliy kurash reja, Basketbol sport turining tarixi va rivojlanishi, Elektr yuritma asoslari. Xoshimov O.O, Nanoo’lchamli klasterlar va kristallar. Nanotexnologiyalar., Mamarajabov Muhammadali Botir o’g’li, 12.1. FLOYD – UORSHELL ALGORITMI
Har qanday tugunlardan barcha tugunlarga bo’lgan masofalarni hisoblash uchun amalda qullaniladi. Algoritm samaradorligi amallar bajarilishi 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 tsikllanib 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.
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 = g
for i = 1 ... n + 1
for j = 0 ... n - 1
for k = 0 ... n - 1
if d[j][k] > d[j][i - 1] + d[i - 1][k]
d[j][k] = d[j][i - 1] + d[i - 1][k]
d matritsa natijasini ekranga chiqarish
Algoritmning dastur kodi:
#include
#include
int main()
{
int n, a[101][101];
ifstream ifs ("input.txt");
ifs>> n;
for(inti=1;i<=n;i++)
for(int j=1;j<=n;j++)
ifs>> a[i][j];
ifs.close();
for(int k=1;k<=n;k++)
for(inti=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
ofstream ofs("output.txt");
for(inti=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
ofs<< a[i][j]<<" ";
ofs<<'\n';
}
ofs.close();
return0;
}
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiya universitut
|
