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
