Kampyuter injinering

---

MUXAMMAD AL-XORAZMIY NOMIDAGI 
TOSHKENT AXBOROT TEXNOLOGIYALARI 
UNIVERSITETI URGANCH FILIALI 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
“KAMPYUTER INJINERING” FAKULTETI 
963-19 GURUH 3-KURS 
TALABASI 
“RAXIMBERGANOV TEMURBEKNING” 
 ALGARITMLARNI LOYIHALASH FANIDAN 
MUSTAQIL ISHI 

---

Mavzu: Eng qisqa yo'llarini topish algoritmlari. 
 
CAL020 guruh talabasi 
Bajardi:XakimovXojiakbar 
Tekshirdi:Ishmuhamedov A. 
Reja: 
1.
Floyd Algoritmi eng qisqa yo'llarini topish algoritmlari haqida 
tushuncha . 
2.
Eng qisqa yo'llarini topish algoritmlari misollar. 
3.
Xulosa 
4.
Foydalanilgan adabiyotlar ro’yhati. 
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'llarni topadi. 

---

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]<="" p=""> 
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.