O'zbekiston respublikasi axborot texnalogiyalari va kommunikatsiyalari rivojlantirish vazirligi muxammad al-xorazmiy nomidagi toshkent axborot texnalogiyalari universiteti. Algoritmlarni loyihalash fanidan

O'ZBEKISTON RESPUBLIKASI AXBOROT TEXNALOGIYALARI VA KOMMUNIKATSIYALARI RIVOJLANTIRISH VAZIRLIGI MUXAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNALOGIYALARI UNIVERSITETI.

Algoritmlarni loyihalash fanidan

Labaratoriya mashg’uloti.

MAVZU: Graflar bilan ishlashning elementar algoritmlari.
Bajardi: CAL 010-L2 guruh

Talabasi: Ilyosov Otabek

Tekshirdi: ____________

Toshkent 2020

Variant №:14

#include

#include

#define SIZE 6

int main()

{

int a[SIZE][SIZE]; // aloqa matritsasi

int d[SIZE]; // minimal masofa

int v[SIZE]; // tashrif buyurgan tepaliklar

int temp, minindex, min;

int begin_index = 0;

system("chcp 1251");

system("cls");

// Aloqa matritsasini ishga tushirish

for (int i = 0; i

{

a[i][i] = 0;

for (int j = i + 1; j

printf("Masofani kiriting %d - %d: ", i + 1, j + 1);

scanf("%d", &temp);

a[i][j] = temp;

a[j][i] = temp;

}

}

// Aloqa matritsasining chiqishi

for (int i = 0; i

{

for (int j = 0; j

printf("%5d ", a[i][j]);

printf("\n");

}

//Vertices va masofalarni ishga tushirish

for (int i = 0; i

{

d[i] = 10000;

v[i] = 1;

}

d[begin_index] = 0;

// Algoritm bosqichi

do {

minindex = 10000;

min = 10000;

for (int i = 0; i

{ // Agar tepalik hali chetlab o'tmagan bo'lsa va vazn kamroq bo'lsa min

if ((v[i] == 1) && (d[i]

{ // Qiymatlarni qayta kiriting

min = d[i];

minindex = i;

}

}

// Topilgan minimal vazn qo'shing

// tepaning joriy vazniga

// va hozirgi minimal yuqori vazn bilan Solishtiring

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);

// Eng qisqa masofani cho'qqilarga chiqarish

printf("\nTepaliklarga eng qisqa masofa: \n");

for (int i = 0; i

printf("%5d ", d[i]);

// Yo'lni tiklash

int ver[SIZE]; // tashrif buyurilgan tepaliklarning bir qatori

int end = 4; // oxirgi yuqori indeks = 5 - 1

ver[0] = end + 1; // dastlabki element-yakuniy tepalik

int k = 1; //oldingi yuqori indeks

int weight = d[end]; // oxirgi tepaning vazni

while (end != begin_index) // dastlabki tepaga etib bormagan

{

for (int i = 0; i

if (a[i][end] != 0) // agar aloqa mavjud bo'lsa

{

int temp = weight - a[i][end]; // avvalgi tepadan yo'lning og'irligini aniqlang

if (temp == d[i]) // agar vazn hisoblangan bo'lsa

{ // shunday qilib, bu yuqoridan o'tish bor edi

weight = temp; // yangi vaznni saqlang

end = i; // avvalgi yuqori qismini saqlang

ver[k] = i + 1; // va uni qatorga yozing

k++;

}

}

}

// Chiqish yo'li (boshlang'ich yuqori k elementlar qator oxirida edi)

printf("\nEng qisqa yo'lni topish\n");

for (int i = k - 1; i >= 0; i--)

printf("%3d ", ver[i]);

getchar(); getchar();

return 0;

}