Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari

Xulosa;

Ushbu laboratoriya ishida men onlay redakdor grafikasida kod chizip qatnashini yani 1.0 korip chiqdimi

13-AMALIY MASHG’ULOT

Eng qisqa yo’lni topish algoritmlari. Sinov turlarini o’rganish
Ishdan maqsad. Ushbu laboratoriya ishida talabalar grafning asosan matritsali usuli bilan tanishib chiqishi kerak.
Qo’yilgan masala. Talabalar topshiriq variantiga mos ravishda graf ustida berilgan amallar asosan bog’langan ro’yhatlar bilan ishlash ko’nikmasiga ega bo’lishlari kerak.
Ish tartibi: Tajriba ishi nazariy
ma’lumotlarini o‘rganish;
berilgan topshiriqning algoritmini ishlab chiqish; C++ dasturlash muhitida dasturni yaratish; natijalarni tekshirish;


/ Floyd algoritm funktsiyasi tavsifi

void Floyd(int n, int **Graph, int **ShortestPath){ int i, j, k;

int Max_Sum = 0;

for ( i = 0 ; i < n ; i++ ) for ( j = 0 ; j < n ; j++ )

Max_Sum += ShortestPath[i][j]; for ( i = 0 ; i < n ; i++ )
for ( j = 0 ; j < n ; j++ )

if ( ShortestPath[i][j] == 0 && i != j ) ShortestPath[i][j] = Max_Sum;

for ( k = 0 ; k < n; k++ )

for ( i = 0 ; i < n; i++ ) for ( j = 0 ; j < n ; j++ )
if ((ShortestPath[i][k] + ShortestPath[k][j]) < ShortestPath[i][j])
ShortestPath[i][j] = ShortestPath[i][k] + ShortestPath[k][j];
}

Agar grafik yo'naltirilmagan bo'lsa, unda transformatsiyalar natijasida olingan barcha matritsalar nosimmetrik bo'lib, shuning uchun faqat asosiy diagonaldan yuqorida joylashgan elementlarni hisoblash kifoya.

Agar grafik qo'shni matritsasi bilan ifodalangan bo'lsa, unda bu algoritmning ishlash vaqti o(n3) buyrug'iga ega, chunki u bir-biriga biriktirilgan uchta tsiklni o'z ichiga oladi.




Xulosa ; Men ushbu Mustaqil ishini bajarish mobaynida eng qisqa yo'llarini topish algoritmlarini bu yo’llar kimlar tomonida oylab topilganini bu yo’llarni nima sababdan oylab topilganini bu yo’llarni turlarini o’rgandim.