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

Algoritmning 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.

1. 
   Yo’l tushunchasi
   
2. 
   Yo’l uzunligi tushunchasi
   
3. 
   Graflarda eng qisqa masofani aniqlash masalasi qanday qo’yiladi?
   
4. 
   Shunga o’hshash masalalar haqida nima deyish mumkin?
   
5. 
   Qisqa masofani aniqlashning Deykstra algoritmi qanday?
   
6. 
   Floyd – Uorshell algoritmini tushuntiring
   
7. 
   Ford – Belmann algoritmi tushuntiring
   
8. 
   Algoritmlar samaradorligi qanday?
   

Adabiyotlar.

1. 
   AdamDrozdek. Data structure and algorithms in C++. Fourthedition. 2013. Chapter 8. 391-490 betlar.
   
2. 
   A computer science portal for geeks. http://www.geeksforgeeks.org/data-structures/#Graph
   
3. 
   http://www.tutorialspoint.com/data_structures_algorithms/graph_data_structure.htm