Kommutatsiya va marshrutizatsiya

Algoritmni bajarilishini tugatish
. Algoritm hech bir balandlikka ishlov 
berish mumkin bo‗lmaganda ishlashni tugatadi. Bu misolda barcha balandliklar 
o‗chirilgan, ammo har qanday misolda ham shunday bo‗ladi deb faraz qilish xato 
bo‗ladi, ayrim balandliklar, agar ularga yetib borish imkoni bo‗lmasa, o‗chirilmay 
qolishi mumkin. Algoritmning natijasi oxirgi rasmdan ko‗rinadi: 1-nchi 
balandlikdan 2-chi balandlikkacha bo‗lgan eng qisqa yo‗l 7 ni, 3-chi 
balandlikkacha yo‗l – 9 ni, 4-chi balandlikkacha yo‗l – 20 ni, 5-chi balandlikkacha 
yo‗l – 20 ni, 6-chi balandlikkacha yo‗l 11 ni tashkil etadi. 
9
8
7
4
5
6
2
3
1
10
11
12
13
14
15
16
3
Жараён Belgi 1 2 3 4 5 6 7 8 9 
0 
L 
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 
Q 
1 
L 
0 9 2 7 ∞ ∞ ∞ ∞ ∞ 
Q 
1 1 1 
2 
L 
0 9 2 7 ∞ 8 7 ∞ ∞ 
Q 
1 1 1 
3 3 
3 
L 
0 9 2 7 ∞ 8 7 23 ∞ 
Q 
1 1 1 
3 3 7 
4 
L 
0 9 2 7 22 8 7 23 ∞ 
Q 
1 1 1 4 3 3 7 
5 
L 
0 9 2 7 11 8 7 20 22 
Q 
1 1 1 6 3 3 6 
6 
6 
L 
0 9 2 7 11 8 7 20 22 
Q 
1 1 1 6 3 3 6 
6 
7 
L 
0 9 2 7 11 8 7 20 21 
Q 
1 1 1 6 3 3 6 
5 
8 
L 
0 9 2 7 11 8 7 20 21 
Q 
1 1 1 6 3 3 6 
5 
R1 
R2 
R3 
R4 
R7 
R6 
R5 
R9 
R8 

---

54 
 
FLOYD ALGORITMINING ISHLASH PRINSIPINI TADQIQ QILISH 
Nazariy ma’lumotlar 
 
Floyd algoritmi - yo‗naltirilgan grafning barcha balandliklari orasidagi eng 
qisqa masofani topish uchun dinamik algoritm hisoblanadi. U 1962 yilda Robert 
Floyd tomonidan ishlab chiqilgan, 1959 yilda Bernard Roy (Bernard Roy) xuddi 
shu algoritmni e‘lon qilgan bo‗lsa-da, ammo bu ahamiyatsiz bo‗lib qoldi. 
Bu algoritm Deykstra algoritmiga qaraganda umumiyroq hisoblanadi, 
chunki u istalgan ikkita tarmoq qurilma orasidagi eng qisqa yo‗llarni topadi. Bu 
algoritmda tarmoq n satrlar va n ustunlarga ega bo‗lgan kvadrat matritsa shaklida 
berilgan. (i, j) element i tugundan ј tugungacha bo‗lgan d
ij
masofaga teng, u agar (i, 
j) joy mavjud bo‗lsa, chekli qiymatga ega va aks holda cheksizlikka teng bo‗ladi. 
Oldin Floyd usulining asosiy g‗oyasini ko‗rsatamiz. Aytaylik, uchta i , j va k 
tugunlar mavjud va ular orasidagi masofalar berilgan (8.1-rasm). Agar d
ij
+ d
jk
ik
tengsizlik bajarilsa, u holda i → k yo‗lni i → ј → k bilan almashtirish tavsiya 
etiladi. Bunday almashtirish (bundan keyin uni shartli ravishda uchburchak 
operator deb ataymiz) Floyd algoritmini bajarish jarayonida muntazam ravishda 
amalga oshiriladi. 
7.12-rasm. Uchburchak operatori 
Floyd algoritmi quyidagi amallarni bajarilishini talab qiladi. 
0-qadam
. Dastlabki D
0 
masofa matritsasi va S
0
tugunlarning ketma-ketlik 
matritsasini aniqlaymiz. Ikkala matritsaning diagonal elementlari "-" belgisi bilan 

---

55 
belgilanadi. U bu elementlarni hisoblashlarda qatnashmasligini ko‗rsatadi. k = 1 
deb olamiz: 
7.13-rasm. Floyd algoritmi bo‘yicha dastlabki holat