Fanidan mavzusida

O ’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA-MAXSUS TA’LIM VAZIRLIGI
_________________________SAMARQAND DAVLAT UNIVERSITETI


KURS ISHI


RAQAMLI TEXNOLOGIYALAR FAKULTETI
“ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN
MAVZUSIDA “_______________________________________________ ”


Guruh: 107-21
Yo’nalish: Dasturiy injiniring
Talabasi:__________________
Tekshirdi: Abdusalomova G._


Samarqand-2022

Mundarija:
Kirish.

1. 
   Floyd Algoritmi eng qisqa yo'llarini topish algoritmlari haqida tushuncha.
   
2. 
   Eng qisqa yo'llarini topish algoritmlarimisollar.
   
3. 
   Graflar ustida amallar. Marshrutlar va zanjirlar.
   
4. 
   Xulosa
   
5. 
   Foydalanilgan adabiyotlarro’yhati.
   

Kirish.
Tabiatda ko‘pincha, narsa va hodisalarning xossalarini o‘rganish jarayonida o‘rganilayotgan ob’yekt elementlarini bir-birlari bilan taqqoslab, ularni birgalikda qarab yoki elementlarni bo‘laklarga ajratib turli xulosalar qilishga to‘g‘ri keladi. Graflar nazariyasi boshqotirmalar va qiziqarli o‘yinlarni o‘rganish jarayonida paydo bo‘lib, hozirgi vaqtda graf tushunchasi yordamida yo‘llar, elektr, axborot va boshqa tarmoqlar, geografik xaritalar, kimyoviy birlashmalar, odamlar va jamiyat orasidagi munosabatlar bilan bog‘liq hamda boshqa ko‘plab masalalarni hal qilish mumkin. Graflar nazariyasi axborot texnologiyalar rivojida muhim ahamiytga ega bo‘lgan diskret matematikaning bir tilidir.
Floyd Algoritmi
Ushbu algoritm ba'zan Floyd-Warshell algoritmi deb ataladi. Floyd-Warshell algoritmi 1962da Robert Floyd va Stiven Uorchell tomonidan ishlab chiqilgan graflarda algoritmdir. Grafning barcha juftlari orasidagi eng qisqa yo'llarni topishga xizmat qiladi. Floyd usuli to'g'ridan-to'g'ri qovurg'alarning ijobiy og'irliklari bo'lgan ustunda, har qanday elementar bo'lmagan (1 qovurg'asidan ko'prog'ini o'z ichiga olgan), eng qisqa yo'l boshqa eng qisqa yo'llardan iborat. Ushbu algoritm Dijkstra algoritmiga nisbatan ancha keng tarqalgan, chunki u har qanday ikki ustun o'rtasida eng qisqa yo'llarnitopadi.
Floyd algoritmida eng qisqa yo'llarning uzunligi hisoblangan NxN matritsasi ishlatiladi. A[i,j] elementi, agar u erda chekka (i, j) bo'lsa,yakuniy qiymatga ega bo'lgan va aks holda abadiylikka teng bo'lgan j ning yuqori qismidan masofaga teng.
Floyd Algoritmi
Algoritmning asosiy g'oyasi. I, j, k ning uchta tepasi bor va ular orasidagi masofa belgilanadi. Agar tengsizlik a[i,k]+a[k,j]j yo'lini i->k->j bilan almashtirish tavsiya etiladi. Qadam 0. A0 masofasining dastlabki matritsasini va S0 vertexlarining ketma-ketligini aniqlang. Har ikkala matritsaning har bir diagonali elementi 0ga teng, shuning uchun bu elementlarning hisob-kitoblarda ishtirok etmasligini ko'rsatmoqda. K = 1 ga ishonamiz.
Asosiy qadam k. k satrini va k ustunini etakchi satr va etakchi ustun sifatida belgilang. Yuqorida tavsiflangan AK-1 matritsasining barcha elementlariga[i, j] almashtirishni ko'rib chiqamiz. Agar tengsizlik a[i,k]+a[k,j]A[i,k]+a[k,j] miqdori uchun A[i,j] elementining Ak-1 matritsasini almashtirish orqali Ak matritsasini yarating] ;
k ga SK-1 element s[i,j] matritsasini almashtirish orqali Sk matritsasini yarating.

Shunday qilib, Floyd algoritmi n yinelemelerini qiladi, a matritsasining i- yinelemesinden keyin, bu yo'llar birinchi dan i-chigacha bo'lgan tepaliklardan o'tishi sharti bilan, har qanday ikki juftlik orasidagi eng qisqa yo'llarning uzunligini o'z ichiga oladi. Har bir iteratsiya bo'ylab barcha juftlar ko'chib o'tadi va ularning orasidagi yo'l i-tepa yordamida kamayadi ( misol 45.2).

Misol 45.2. Floyd algoritmini namoyish qilish

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