|
O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti
|
| bet | 63/163 | | Sana | 16.01.2024 | | Hajmi | 18,84 Mb. | | #138868 |
Bog'liq O zbekiston respublikasi oliy va o rta maxsus ta lim vazirligi tAlgoritmning dastur kodi:
#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;
}
Nazorat savollar.
Graflarda eng qisqa masofani aniqlash masalasi?
Qisqa masofani aniqlashning Deykstra algoritmi qanday?
Floyd – Uorshell algoritmi
Ford – Belmann algoritmi
Algoritmlar samaradorligi qanday?
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
http://www.tutorialspoint.com/data_structures_algorithms/graph_data_structure.htm
13-ma’ruza. Yo’naltirilmagan graflar.
Minimal narxli daraxtlar skeleti.
|
| |
