13 –mavzu. Graflarda eng qisqa yo‘lni aniqlash algoritmlari. Lug‘atlar va ularni amalga oshirish. Reja



Yüklə 141,47 Kb.
səhifə3/6
tarix23.11.2022
ölçüsü141,47 Kb.
#70095
1   2   3   4   5   6
13 –mavzu. Graflarda eng qisqa yo‘lni aniqlash algoritmlari. Lug

2.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;
}


Yüklə 141,47 Kb.

Dostları ilə paylaş:
1   2   3   4   5   6




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin