Graflarda eng qisqa yo'lni aniqlashning deykstra algoritmlari guruh: swd025 bajardi: yaxshiliqov sh tekshirdi: ganixodjaeva d

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[0] = 0 //0 -tanlangan tugun d = g[0] mark[0] = True for i = 1 .. n - 1 mark[i] = False for i = 1 .. n - 1 v = -1 for i = 0 .. n - 1 if (not mark[i]) and ((v == -1) or (d[v] > d[i])) v = i mark[v] = True for i = 0 ... n - 1 if d[i] > d[v] + g[v][i] d[i] = d[v] + g[v][i] d massiv natijasini ekranga chiqarish Deykstra algoritmiga natija olish qadamlari
#include #include #include #include int main() { //******************************** int a[500][500],d[500]={0}, n,s,f,flag[500],l,min1=100000000,nmin=0; for(inti=0;i<=500;i++) flag[i]=1; ifstream ifs ("input.txt"); ifs>> n >> s >> f; for(inti=1;i<=n;i++) for(int j=1;j<=n;j++) { ifs>> a[i][j]; if(a[i][j]==-1&&i!=j) a[i][j]=32000; } ifs.close(); //**********************************
l=s; for(inti=1;i<=n;i++) d[i]=a[l][i]; flag[l]=0; for(inti=1;i<=n-1;i++) { min1=100000000; nmin=l; for(int j=1;j<=n;j++) if(flag[j]!=0&& min1>d[j]) { min1=d[j]; nmin=j; } l=nmin; flag[l]=0; for(int j=1;j<=n;j++) if(flag[j]!=0) d[j]=min(d[j],a[l][j]+d[l]); } ofstream ofs("output.txt"); if(d[f]==32000) ofs<<"-1"; else ofs<< d[f]; ofs.close(); return 0; }
Algoritmning dastur kodi:
Adabiyotlar.

• AdamDrozdek. Data structure and algorithms in C++. Fourthedition. 2013. Chapter 8. 391-490 betlar.
• A computer science portal for geeks. http://www.geeksforgeeks.org/data-structures/#Graph

E’TIBORINGIZ UCHUN RAHMAT