Mavzu: Daraxtsimon ma'lumotlar tuzilmasi. Graf tushunchasi va uning ko'rinishlari. Eng yaqin yo’lni aniqlash masalalari

Masalani yechish (algoritm, dastur kodi, natija).

Ushbu grafdagi 1 va 4-tugunlar orasidagi eng qisqa yo’l zanjirini toping. (Deykstr algoritmi yordamida).

5

3

1

2

4

6

14

12

8

4

3

9

11

7

5

Izoh. Har birini qadamma-qadam ko’rsating.

#include

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define SIZE 6
int main()
{
int a[SIZE][SIZE];
int d[SIZE];
int v[SIZE];
int temp, minindex, min;
int begin_index = 0;
system("chcp 1251");
system("cls");
for (int i = 0; i{
a[i][i] = 0;
for (int j = i + 1; jprintf("Masofani kiriting %d - %d: ", i + 1, j + 1);
scanf("%d", &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
for (int i = 0; i{
for (int j = 0; jprintf("%5d ", a[i][j]);
printf("\n");
}
for (int i = 0; i{
d[i] = 10000;
v[i] = 1;
}
d[begin_index] = 0;
do {
minindex = 10000;
min = 10000;
for (int i = 0; i{
if ((v[i] == 1) && (d[i]{
min = d[i];
minindex = i;
}
}

if (minindex != 10000)

{
for (int i = 0; i{
if (a[minindex][i] > 0)
{
temp = min + a[minindex][i];
if (temp < d[i])
{
d[i] = temp;
}
}
}
v[minindex] = 0;
}
} while (minindex < 10000);
printf("\nNuqtalargacha eng qisqa masofalar: \n");
for (int i = 0; iprintf("%5d ", d[i]);
int ver[SIZE];
int end = 4;
ver[0] = end + 1;
int k = 1;
int weight = d[end];

while (end != begin_index)

{
for (int i = 0; iif (a[i][end] != 0)
{
int temp = weight - a[i][end];
if (temp == d[i])
{
weight = temp;
end = i;
ver[k] = i + 1;
k++;
}
}
}
printf("\nEng qisqa yo'lning kelib chiqishi\n");
for (int i = k - 1; i >= 0; i--)
printf("%3d ", ver[i]);
getchar(); getchar();
return 0;
}
Natija:

4. 
   Xulosa: Bu mustaqil ishini bajarish jaronida men binar algortmlari bilan tanishdim. Bu algorirmlarni dasturlashda juda kerakli aglormlar ekanligini tushunib yetdim. O’z masalamni yechish moboynida men Deykstr algoritmini mukammal o’rgandim.
   

1. 
   Foydalanilgan adabiyotlar.
   

1. 
   Qudratxo’ja Musayev (“sralash algoritmlari”)
   
2. 
   Jahongir Soataliyev (sralash algoritmlarining 5 xil usuli)
   
3. 
   M.M.Aripov, N.A.Otaxanov (DASTURLASH ASOSLARI)Introduction to
   
4. 
   Programming with C++ (Myprogramminglab) 3rd Edition by Y. Daniel Liang (Author), Y. Liang (Author)
   
5. 
   C++ maruza Qudrat Abdurahimov
   
6. 
   https://www.geeksforgeeks.org/selection-sort/