Graflarda eng qisqa yo‘lni aniqlash algoritmlari. Lug‘atlar va ularni amalga oshirish

Algoritmning psevdokodi: g grafni o’qib olamiz
// g[0 ... n - 1][0 ... n - 1] - qirralar 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(int i=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(int i=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(int i=1; i<=n;i++) {
for(int j=1; j<=n;j++)
ofs<< a[i][j]<<" ";
ofs<<'\n';
}
ofs.close();
return 0;
}
2.2. FORD – BELMANN ALGORITMI
Berilgan tugundan (uni 0 deb bilgilaymiz) barcha boshqa tugunlarga bo’lgan qisqa masofalarni hisoblash uchun amalda qo`llaniladi. Algoritm samaradorligi amallar bajarilishi bo’yicha n*m tartibli hisoblanadi. Bu algoritmda ham qirralar o’girlik qiymatlari manfiy bo’lishi mumkin va halqa ko’rinishida berilmagan bo’lishi lozim.
Algoritm g’oyasi:
d[0 .. n–1] masofalar massivi har i-chi qadamda javobini saqlash uchun ishlatiladi va har qadamda i-dan oshmagan qirralar soni ishtirokida masofa hisoblash uchun foydalaniladi. Agar j-tugunga yo’l mavjud bo’lmasa u holda d[j] = 2000000000 (yani cheksiz qiymatga teng deb hisoblanadi). Birinchi qadamda d massiv cheksiz qiymatlar bilan to’ldirilib olinadi. Va har keyingi qadamda qirralar ko’rib chiqiladi va masofani yangilash uchun tekshiriladi. Agar qirradan ushbu tugunga marshruti mavjud bo’lsa u holda masofalar solishtiriladi. Yangi qiymat kichik bo’lsa u holda massiv yangilanadi. Shuni aytish ham lozimki, qisqa masofani aniqlashda halqa ishtirok etilmaydi.